#P22702. [ARC132E] Paw

[ARC132E] Paw

题目链接

题意

一个长度维 nn 的字符串 ss,其中只包含 .<> 这三种字符。

不断进行如下操作:

  • 等概率随机选择一个 . 作为起点,等概率随机选择方向向左或向右。

  • 从选择的起点开始沿选择的方向运动,直到遇到下一个 . 或者超出范围。

  • 修改走过的这些字符,如果是向左运动则全部改成 < ,否则全部改成 > 。特别的,起点的 . 要修改,终点的 . 不修改。

每次操作后 ss 中的 . 数量会减少一 ,若干次操作后 ss 中只剩下 <> 两种字符。计算此时 < 的期望数量,答案一定是个有理数,输出答案对 998244353998244353 取模的结果。

输入格式

第一行一个整数 nn

第二行一个长度为 nn 的字符串 ss

输出格式

一个整数答案。

样例

5
><.<<
3
20
>.>.<>.<<.<>.<..<>><
848117770

数据范围

1n1051\le n\le 10^5