AT_pakencamp_2022_day3_f Cycle and Xor

给定一个长度为 $N$ 的数列 $A = (A_0, A_1, \ldots, A_{N-1})$，其中每个元素都是 $0$ 以上 $2^M$ 未满的整数，求满足以下条件的数列个数，并对 $998244353$ 取余后输出。 - 对于所有整数 $i\ (0 \leq i \leq 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$ 表示按位异或（XOR）运算。 按位异或（XOR）运算是指，对于非负整数 $A$ 和 $B$，他们的按位异或 $A \oplus B$ 定义如下： - 若 $A,B$ 的二进制表示中第 $2^k$ 位（$k \geq 0$），只有一方为 $1$，则该位为 $1$，否则为 $0$。 例如，$3 \oplus 5 = 6$（用二进制表示为：$011 \oplus 101 = 110$）。

输入以如下格式经标准输入给出。 > $N\ M\ T_0\ U_0\ T_1\ U_1\ \vdots\ T_{N-1}\ U_{N-1}$

输出答案。

### 样例解释 1 作为 $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 \leq N \leq 2 \times 10^5$ - $1 \leq M \leq 30$ - $0 \leq T_i < U_i < 2^M$ - 输入均为整数。 由 ChatGPT 5 翻译