E - Paw Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

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

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

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

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

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

すぬけくんが操作を終えた時の、左向きの足跡がついたマスの数の期待値を \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 文字以上含む

入力

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

n
s

出力

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

入力例 1

5
><.<<

出力例 1

3

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

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

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

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

入力例 2

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

出力例 2

848117770

Score : 800 points

Problem Statement

There are n squares arranged in a row. Each square has a left- or right-pointing footprint or a hole. The initial state of each square is described by a string s consisting of ., <, >. If the i-th character of s is ., the i-th square from the left has a hole; if that character is <, that square has a left-pointing footprint; if that character is >, that square has a right-pointing footprint.

Snuke, the cat, will repeat the following procedure until there is no more square with a hole.

  • Step 1: Choose one square with a hole randomly with equal probability.
  • Step 2: Fill the hole in the chosen square, stand there, and face to the left or right randomly with equal probability.
  • Step 3: Keep walking in the direction Snuke is facing until he steps on a square with a hole or exits the row of squares.

Here, the choices of squares and directions are independent of each other.

When Snuke walks on a square (without a hole), that square gets a footprint in the direction he walks in. If the square already has a footprint, it gets erased and replaced by a new one. For example, in the situation >.<><.><, if Snuke chooses the 6-th square from the left and faces to the left, the 6-th, 5-th, 4-th, 3-rd squares get left-pointing footprints: >.<<<<><.

Find the expected value of the number of left-pointing footprints when Snuke finishes the procedures, modulo 998244353.

Notes

When the sought expected value is represented as an irreducible fraction p/q, there uniquely exists an integer r such that rq\equiv p ~(\text{mod } 998244353) and 0 \leq r \lt 998244353 under the Constraints of this problem. This r is the value to be found.

Constraints

  • 1 \leq n \leq 10^5
  • s is a string of length n consisting of ., <, >.
  • s contains at least one ..

Input

Input is given from Standard Input in the following format:

n
s

Output

Print the expected value of the number of left-pointing footprints, modulo 998244353.

Sample Input 1

5
><.<<

Sample Output 1

3

In Step 1, Snuke always chooses the only square with a hole.

If Snuke faces to the left in Step 2, the squares become <<<<<, where 5 squares have left-pointing footprints.

If Snuke faces to the right in Step 2, the squares become ><>>>, where 1 square has a left-pointing footprint.

Therefore, the answer is \frac{5+1}{2}=3.

Sample Input 2

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

Sample Output 2

848117770