F - Cycle and Xor Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

0 以上 2^M 未満の整数からなる長さ N の数列 A=(A_0,A_1,\ldots,A_{N-1}) であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • すべての整数 i\ (0 \le i \le N-1) について、 A_i \oplus A_{(i+1) \bmod N} \neq T_i かつ A_i \oplus A_{(i+1) \bmod N} \neq U_i が成り立つ

ただし \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 30
  • 0 \le T_i < U_i < 2^M
  • 入力は全て整数

入力

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

N M
T_0 U_0
T_1 U_1
\vdots
T_{N-1} U_{N-1}

出力

答えを出力せよ。

入力例 1

3 2
0 1
1 2
2 3

出力例 1

8

A としてありうるのは (0,2,1),(0,3,0),(1,3,0),(1,2,1),(2,0,3),(2,1,2),(3,1,2),(3,0,3) の 8 通りです。

入力例 2

3 1
0 1
0 1
0 1

出力例 2

0

入力例 3

5 10
31 415
92 653
58 979
32 384
62 643

出力例 3

552613140