AT_arc132_e [ARC132E] Paw

[problemUrl]: https://atcoder.jp/contests/arc132/tasks/arc132_e $ n $ 個のマスが一列に並んでいます。それぞれのマスには右向きか左向きの足跡がついているか、穴が空いているかのいずれかです。 各マスの最初の状態は `.`, `` からなる文字列 $ s $ で表され、$ s $ の $ i $ 文字目が `.` であるとき左から $ i $ マス目に穴が空いていることを、`` であるとき右向きの足跡がついていることを表します。 猫のすぬけくんは、穴の空いているマスがなくなるまで次の操作を繰り返します。 - Step $ 1 $: 穴の空いているマスのうち $ 1 $ マスを等確率でランダムに選ぶ。 - Step $ 2 $: 選んだマスの穴を埋め、そこに立ち、等確率でランダムに左か右を向く。 - Step $ 3 $: 穴の空いているマスの上に乗るか、マスの外に出るまで、向いている方向に歩き続ける ただし、マスの選び方も向く方向の選び方も、互いに独立とします。 すぬけくんが（穴の空いていない）マスの上を歩くとき、そのマスには歩いた向きに足跡が付きます。 すでに足跡がついているマスであっても、もともとついている足跡が消えて、新しく足跡が付きます。 例えば、`>..

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

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

### 注意 求める期待値が既約分数 $ 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 $ です。