問題文

1 枚の円形のピザがあり、その円周上には円周をちょうど N 等分するように、N 個の点 P_1, P_2, \cdots P_N があります。

最初、ピザに切れ目は入っておらず、次のルールに従って、ピザを M 回切断します。

• i (1 \le i \le M) 回目の切断では、実数 \theta を 0 \lt \theta \lt \pi を満たす実数の一様分布からランダムに選び、点 P_{A_i} におけるピザの円周の接線を 点 P_{A_i} を中心として反時計回りに \theta だけ回転させた直線に沿ってピザを切断する。

全ての切断が終了した後のピザの分割数の期待値を mod 998244353 で求めてください。

制約

• 入力は全て整数
• 1 \le N \le 998244352
• 1 \le M \le 3 \times 10^5
• 1 \le A_i \le N

入力例 1

4 2
1 3

出力例 1

748683268

ピザは \frac{3}{4} の確率で 3 分割、\frac{1}{4} の確率で 4 分割されるため、求める期待値は \frac{13}{4} となります。

入力例 2

2 2
1 1

出力例 2

3

配列 A は同じ整数を複数含むこともあります。

入力例 3

9 7
3 1 4 1 5 9 2

出力例 3

49296032