AT_pakencamp_2024_day3_1_a Many Many Shiomusubi

以下の問題を考えます。 > 正整数 $ N $ 、長さ $ N $ の正整数列 $ S=(S_1,S_2,\dots,S_N) $ 、長さ $ N $ の $ \mathtt{L} $ または $ \mathtt{R} $ のみからなる文字列 $ D=D_1D_2\dots D_N $ が与えられます。 > > 数直線上に $ N $ 個のしおむすびがあり、 $ 1,2,\dots,N $ と番号が付いています。しおむすび $ i $ は座標 $ i $ にあり、その大きさは $ S_i $ です。しおむすび $ i $ の向きは文字 $ D_i $ で表され、 $ D_i=\mathtt{L} $ のとき数直線の負の方向を、 $ D_i=\mathtt{R} $ のとき数直線の正の方向を向いています。 > > これから、しおむすびが動きます。しおむすび $ i $ は秒速 $ S_i $ で向いている向きに進みます。 複数のしおむすびが同一座標にあるとき、以下の事象が発生します。 > > - その座標にある大きさが最大のしおむすびのうち最も番号が大きいものが、その座標にある他のしおむすびを食べる。食べられたしおむすびは消滅する。これによって残ったしおむすびの向きや大きさが変化することはない。 > > $ 10^{100} $ 秒後、残っているしおむすびの大きさの総積を求めてください。 整数 $ N,M $ が与えられます。 $ 1\leq S_i\leq M $ $ (1\leq i\leq N) $ を満たす入力は $ (2M)^N $ 通り存在しますが、それらすべてに対する上記の問題の答えの総和を $ 998244353 $ で割ったあまりを求めてください。

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

答えを出力せよ。

### 部分点 - $ N,M \leq 300 $ を満たすデータセットに正解した場合は、 $ 15 $ 点与えられる。 - $ N,M \leq 3000 $ を満たすデータセットに正解した場合は、上記とは別に $ 15 $ 点与えられる。 - 追加制約のないデータセットに正解した場合は、上記とは別に $ 70 $ 点与えられる。 ### Sample Explanation 1 考えるべき入力 $ 16 $ 通りについて、残るしおむすびの大きさの総積は以下です。 $ S=(1,1) $ $ S=(1,2) $ $ S=(2,1) $ $ S=(2,2) $ $ D=\mathtt{LL} $ $ 1 $ $ 2 $ $ 2 $ $ 4 $ $ D=\mathtt{LR} $ $ 1 $ $ 2 $ $ 2 $ $ 4 $ $ D=\mathtt{RL} $ $ 1 $ $ 2 $ $ 2 $ $ 2 $ $ D=\mathtt{RR} $ $ 1 $ $ 2 $ $ 2 $ $ 4 $ よって、答えは $ 34 $ です。 ### Sample Explanation 2 総和を $ 998244353 $ で割ったあまりを求めることを忘れないでください。 ### Constraints - $ 1 \leq N,M\leq 2\times 10^5 $ - 入力はすべて整数