配点 : $1000$ 点

問題文

PCT 君は以下の問題を作りました。

Xor Optimization Problem長さ $N$ の非負整数列 $A_1,A_2,...,A_N$ が与えられる。$A$ の要素を好きな個数選ぶとき、選んだ値の $\mathrm{XOR}$ が取りうる最大値はいくらか？

この問題は、Nyaan さんにとっては簡単だったため PCT 君は以下のように改題しました。

Many Xor Optimization Problems長さ $N$ かつ全ての要素が $0$ 以上 $2^M-1$ 以下である整数列は $2^{NM}$ 通り存在しますが、その全てに対して Xor Optimization Problem を解いた時の解の総和を $998244353$ で割ったあまりを求めてください。

Many Xor Optimization Problems を解いてください。

制約

• $1 \le N,M \le 250000$
• 入力は全て整数である。

入力

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

$N$ $M$

出力

答えを出力してください。

2 1

3

長さが $2$ かつ全ての要素が $0$ 以上 $1$ 以下である整数列全てに対して Xor Optimization Problem を解きます。

• $A=(0,0)$ の時の解は $0$
• $A=(0,1)$ の時の解は $1$
• $A=(1,0)$ の時の解は $1$
• $A=(1,1)$ の時の解は $1$

よって、$0+1+1+1=3$ が解となります。

3 4

52290

1234 5678

495502261