题目描述

$n$ 個のマスが一列に並んでいます。それぞれのマスには右向きか左向きの足跡がついているか、穴が空いているかのいずれかです。 各マスの最初の状態は ., <, > からなる文字列 $s$ で表され、$s$ の $i$ 文字目が . であるとき左から $i$ マス目に穴が空いていることを、< であるとき左向きの足跡がついていることを、> であるとき右向きの足跡がついていることを表します。

猫のすぬけくんは、穴の空いているマスがなくなるまで次の操作を繰り返します。

• Step $1$: 穴の空いているマスのうち $1$ マスを等確率でランダムに選ぶ。
• Step $2$: 選んだマスの穴を埋め、そこに立ち、等確率でランダムに左か右を向く。
• Step $3$: 穴の空いているマスの上に乗るか、マスの外に出るまで、向いている方向に歩き続ける

ただし、マスの選び方も向く方向の選び方も、互いに独立とします。

すぬけくんが（穴の空いていない）マスの上を歩くとき、そのマスには歩いた向きに足跡が付きます。 すでに足跡がついているマスであっても、もともとついている足跡が消えて、新しく足跡が付きます。 例えば、>.<><.>< という状態で、すぬけくんが左から $6$ マス目を選んで左を向いたとき、左から $6,5,4,3$ マス目に左向きの足跡がつき、>.<<<<>< となります。

すぬけくんが操作を終えた時の、左向きの足跡がついたマスの数の期待値を $\mathrm{mod~}\ 998244353$ で求めてください。

输入格式

入力は以下の形式で標準入力から与えられる。

$n$ $s$

输出格式

左向きの足跡がついたマスの数の期待値を $\mathrm{mod~}\ 998244353$ で出力せよ。

题目大意

有 $n$ 个方块排列在一排。每个正方形都有一个向左或向右的脚印或一个洞，以 $<,>,.$ 表示。

Snuke，将重复下面的程序，直到不再有一个有洞的方块。

1. 以相等的概率随机选择一个有洞的正方形。
2. 填上所选正方形的洞，站在那里，并以相同的概率随机面向左边或右边。
3. 沿着Snuke所面对的方向一直走，直到他踩到一个有洞的方块或离开这排方块。

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

当 Snuke 踩到一个方块（没有洞）时，该方块在他行走的方向上会有一个脚印。如果该方块已经有了一个脚印，那么它就会被抹去并被一个新的脚印取代。

当Snuke完成这些程序时，求向左的脚印数量的预期值。

• $n\leq10^5$

5
><.<<

3

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

848117770

提示

注意

求める期待値が既約分数 $p/q$ で表されるとき、$rq\equiv\ p\ ~(\text{mod\ }\ 998244353)$ かつ $0\ \leq\ r\ \lt\ 998244353$ を満たす整数 $r$ がこの問題の制約のもとで一意に定まります。 この $r$ が求める値です。

制約

• $1\ \leq\ n\ \leq\ 10^5$
• $s$ は ., <, > からなる長さ $n$ の文字列
• $s$ は . を $1$ 文字以上含む

Sample Explanation 1

Step $1$ では、すぬけくんは穴の空いている唯一のマスを必ず選びます。 Step $2$ ですぬけくんが左を向いたとき、操作後のマスの状態は <<<<< となります。 このとき、左向きの足跡がついたマスの数は $5$ です。 Step $2$ ですぬけくんが右を向いたとき、操作後のマスの状態は ><>>> となります。 このとき、左向きの足跡がついたマスの数は $1$ です。 よって、答えは $\frac{5+1}{2}=3$ です。