配点 : 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