問題文

以下の問題を考えます。

正整数 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 で割ったあまりを求めてください。

制約

• 1 \leq N,M\leq 2\times 10^5
• 入力はすべて整数

部分点

• N,M \leq 300 を満たすデータセットに正解した場合は、15 点与えられる。
• N,M \leq 3000 を満たすデータセットに正解した場合は、上記とは別に 15 点与えられる。
• 追加制約のないデータセットに正解した場合は、上記とは別に 70 点与えられる。

入力例 1

2 2

出力例 1

34

考えるべき入力 16 通りについて、残るしおむすびの大きさの総積は以下です。

よって、答えは 34 です。

入力例 2

200000 200000

出力例 2

815432809

総和を 998244353 で割ったあまりを求めることを忘れないでください。