AT_arc227_e [ARC227E] Shift and XOR Switches

有一个长度为 $N$ 的序列 $B=(B_1,B_2,\ldots,B_N)$，其元素只包含 $0$ 和 $1$。初始时，$B_1=1$，其余所有元素均为 $0$。 现在有 $M$ 个开关，每个开关 $i$ 上写有整数 $A_i$（$1 \le i \le M$）。每当按下第 $i$ 个开关时，对于所有满足 $1 \le j \le N$ 的整数 $j$，根据操作执行前的当前状态，同时进行如下操作： $$ B_j \leftarrow \begin{cases} B_j \oplus B_{j-A_i} & (A_i < j), \\ B_j & (j \leq A_i) \end{cases} $$ 其中 $\oplus$ 表示按位异或。 每个开关可以按 $0$ 次或 $1$ 次，开关的按下顺序可以任意。 请问，最终可能得到多少种不同的序列 $B$，答案对 $998244353$ 取模。 ::::info[什么是按位异或 $ \mathrm{XOR} $ 操作？] 非负整数 $A$ 与 $B$ 的按位异或，记作 $A \oplus B$，定义如下： - 记 $A$、$B$ 的二进制表示，在每一位 $2^k$ 位置（$k \geq 0$），如果 $A$、$B$ 在该位上有且仅有一个为 $1$，则 $A \oplus B$ 的该位为 $1$，否则为 $0$。 例如，$3 \oplus 5 = 6$（二进制表示 $011 \oplus 101 = 110$）。对于 $k$ 个非负整数 $p_1, p_2, p_3, \dots, p_k$ 的按位异或，定义为 $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$，并且可以证明无论按什么顺序异或都得到相同结果。 ::::

输入按以下格式从标准输入读取： > $N$ $M$ > $A_1$ $A_2$ $\ldots$ $A_M$

输出最终可能得到的不同 $B$ 序列数量，对 $998244353$ 取模。

### 样例解释 1 共有四种可能的最终序列： - $(1,0,0,0)$ - $(1,0,1,0)$ - $(1,0,0,1)$ - $(1,0,1,1)$ ### 样例解释 2 共有两种可能的最终序列：$(1,0)$ 和 $(1,1)$。 ### 数据范围 - $2 \le N \le 2 \times 10^5$ - $1 \le M \le 2 \times 10^5$ - $1 \le A_i < N \quad (1 \le i \le M)$ - 所有输入均为整数。 由 ChatGPT 5 翻译