配点 : $800$ 点

問題文

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

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

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

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

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

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

注意

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

制約

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

入力

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

$n$

$s$

出力

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

5
><.<<

3

Step $1$ では、すぬけくんは穴の空いている唯一のマスを必ず選びます。

Step $2$ ですぬけくんが左を向いたとき、操作後のマスの状態は <<<<< となります。 このとき、左向きの足跡がついたマスの数は $5$ です。

Step $2$ ですぬけくんが右を向いたとき、操作後のマスの状態は ><>>> となります。 このとき、左向きの足跡がついたマスの数は $1$ です。

よって、答えは $\frac{5+1}{2}=3$ です。

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

848117770