AT_utpc2024_o One Different Inequality

整数 $ N $ と、`` からなる長さ $ N-1 $ の文字列 $ S $ が与えられます。 $ (1,2,\dots,N) $ の順列 $ P=(P_1,P_2,\dots,P_N) $ を考えます。 $ P $ が以下の条件を満たすとき、 $ P $ は**良い順列**であるといいます。 - 全ての $ i\ (1 \leq i \leq N-1) $ について、 $ S $ の $ i $ 文字目が `` ならば $ P_i > P_{i+1} $ が成り立つ。 また、 $ P $ が以下の条件をすべて満たすとき、 $ P $ は**素晴らしい順列**であるといいます。 - $ P $ は良い順列である。 - $ |P_i-P_{i+1}|=1 $ を満たす $ i\ (1 \leq i \leq N-1) $ の個数が良い順列の中で最大である。 素晴らしい順列の個数を $ 998244353 $ で割った余りを求めてください。

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

答えを $ 1 $ 行に出力せよ。

### 部分点 - 追加の制約 $ 2 \leq N \leq 10000 $ を満たすデータセットに正解した場合は $ 20 $ 点が与えられる。 ### Sample Explanation 1 良い順列の例としては $ (1,2,5,4,3) $ や $ (2,3,5,4,1) $ があげられます。 $ |P_i-P_{i+1}|=1 $ を満たす $ i $ の個数はそれぞれ $ 3,2 $ 個です。 良い順列における $ |P_i-P_{i+1}|=1 $ を満たす $ i $ の個数の最大値は $ 3 $ 個であることが証明でき、素晴らしい順列は $ (1,2,5,4,3) $ と $ (3,4,5,2,1) $ の $ 2 $ つになります。 ### Constraints - $ N $ は整数 - $ 2 \leq N \leq 2 \times 10^5 $ - $ S $ は `` からなる長さ $ N-1 $ の文字列