题目描述

有 $n$ 个方块排成一行。每个方块上可能有一个左向或右向的脚印，或者有一个洞。每个方块的初始状态由一个字符串 $s$ 描述，字符串 $s$ 由 .、< 和 > 组成。如果 $s$ 的第 $i$ 个字符是 .，表示从左数第 $i$ 个方块上有一个洞；如果 $s$ 的第 $i$ 个字符是 <，表示从左数第 $i$ 个方块上有一个向左的脚印；如果 $s$ 的第 $i$ 个字符是 >，表示从左数第 $i$ 个方块上有一个向右的脚印。

猫 Snuke 会重复以下过程，直到没有带洞的方块为止。

• 第一步：以等概率随机选择一个带洞的方块。
• 第二步：在选择的方块上填充洞，并且以等概率随机选择一个方向朝向左侧或右侧。
• 第三步：沿着 Snuke 朝向的方向行走，直到踩到一个带洞的方块，或者走出方块的序列。

这里，选择方块和选择方向是相互独立的。

当 Snuke 走到一个方块（没有洞）时，该方块会获得他行走方向上的脚印。如果该方块已经有脚印，则脚印会被清除并替换为一个新的脚印。例如，在情况 >.<><.>< 中，如果 Snuke 选择从左数第 $6$ 个方块并朝向左侧，那么第 $6$、第 $5$、第 $4$、第 $3$ 个方块得到的脚印为向左的脚印：>.<<<<><。

计算当 Snuke 完成以上过程后，向左的脚印数的期望值，对 $998244353$ 取模。

注意事项

当期望值可以表示成最简分数形式 $p/q$ 时，在本问题的约束条件下，唯一存在一个整数 $r$ 使得 $rq\\equiv p ~(\\text{mod } 998244353)$ 并且 $0 \\leq r \\lt 998244353$。$r$ 就是要找到的结果。

约束条件

• $1 \\leq n \\leq 10^5$
• $s$ 是长度为 $n$ 的字符串，由 .、< 和 > 组成。
• $s$ 至少包含一个 .。

输入

从标准输入中以以下格式给出输入：

$n$ $s$

输出

输出向左的脚印数的期望值，对 $998244353$ 取模。

示例输入1

5
><.<<

示例输出1

3

在第一步中，Snuke 总是只能选择唯一一个带洞的方块。

如果 Snuke 在第二步朝向左侧，那么方块会变成 <<<<<，其中有 $5$ 个方块获得了向左的脚印。

如果 Snuke 在第二步朝向右侧，那么方块会变成 ><>>>，其中有 $1$ 个方块获得了向左的脚印。

因此，答案为 $\\frac{5+1}{2}=3$。

示例输入2

20
>.>.<>.<<.<>.<..<>><

示例输出2

848117770