AT_arc132_e.[ARC132E] Paw

有 $n$ 个格子排成一行。每个格子要么有一个向右的脚印，要么有一个向左的脚印，要么是一个洞。每个格子的初始状态由一个只包含 .、<、> 的字符串 $s$ 表示，$s$ 的第 $i$ 个字符为 . 时，表示从左起第 $i$ 个格子是一个洞；为 < 时，表示该格子有一个向左的脚印；为 > 时，表示该格子有一个向右的脚印。

猫“すぬけくん”会不断重复以下操作，直到所有洞都被填满：

• Step $1$：从所有有洞的格子中，等概率随机选择一个格子。
• Step $2$：填上选中的洞，并站在该格子上，等概率随机选择面向左或右。
• Step $3$：朝着所面向的方向一直行走，直到走到下一个有洞的格子或走出格子范围。

注意，格子的选择和朝向的选择是相互独立的。

当すぬけくん走过一个没有洞的格子时，该格子会留下他行走方向的脚印。如果该格子原本就有脚印，则原有的脚印会被覆盖为新的脚印。例如，状态为 >.<><.>< 时，如果すぬけくん选择了从左起第 $6$ 个格子并面向左，则第 $6,5,4,3$ 个格子会被覆盖为向左的脚印，状态变为 >.<<<<><。

请你求出所有洞都被填满后，最终留下向左脚印的格子数的期望值，并对 $998244353$ 取模输出。

输入为一行，格式如下：

$n$ $s$

输出最终留下向左脚印的格子数的期望值，对 $998244353$ 取模。

注意

如果所求期望值可以表示为既约分数 $p/q$，则输出满足 $rq\equiv p\pmod{998244353}$ 且 $0\leq r<998244353$ 的整数 $r$。这个 $r$ 在本题的约束下是唯一的。你需要输出的就是这个值。

约束条件

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

样例解释 1

在 Step $1$，すぬけくん只能选择唯一的那个洞。在 Step $2$，如果他面向左，操作后格子的状态为 <<<<<，此时向左脚印的格子数为 $5$；如果他面向右，操作后格子的状态为 ><>>>，此时向左脚印的格子数为 $1$。因此，答案为 $\frac{5+1}{2}=3$。

由 ChatGPT 4.1 翻译