L - X and Xor Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

0 以上 2^M 未満の整数からなる長さ N の数列 A すべてについて以下の値を考え、その総和を 998244353 で割った余りを求めてください。

  • (A_1\times A_2) \oplus (A_2\times A_3) \oplus \ldots \oplus (A_{N-1}\times A_N) を 2^M で割った余り

ただし \oplus はビット単位 \mathrm{XOR} 演算を表します。

ビット単位 \mathrm{XOR} 演算とは

非負整数 A,B のビット単位 \mathrm{XOR} 演算、A\oplus B は、以下のように定義されます。

  • A\oplus B を二進表記した際の 2^k\ (k\geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。

例えば、3\oplus 5 = 6 となります（二進表記すると: 011\oplus 101 = 110)。

制約

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

入力

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

N M

出力

答えを出力せよ。

入力例 1

2 1

出力例 1

1

A=(1,1) の場合のみ A_1\times A_2 = 1 で、それ以外の場合は 0 であるため、答えは 1 です。

入力例 2

2 2

出力例 2

16

入力例 3

314 159

出力例 3

856758166