AT_arc227_e.Shift and XOR Switches

There is a length-$N$ sequence $B=(B_1,B_2,\ldots,B_N)$ consisting of $0$ and $1$. Initially, $B_1=1$, and all other elements are $0$.

There are $M$ switches, and the integer $A_i$ is written on switch $i$ ($1 \le i \le M$). When switch $i$ is pressed, using the state immediately before the operation, $B_j$ is simultaneously changed as follows for every integer $j$ satisfying $1 \le j \le N$:

\[ B_j \leftarrow \begin{cases} B_j \oplus B_{j-A_i} & (A_i \lt j),\\ B_j & (j \le A_i) \end{cases} \]

Each switch can be pressed zero times or once, and the switches may be pressed in any order.

Find the number, modulo $998244353$, of possible final sequences $B$.

What is the bitwise $\mathrm{XOR}$ operation?

The bitwise $\mathrm{XOR}$ of non-negative integers $A$ and $B$, denoted $A \oplus B$, is defined as follows:

• The digit in the $2^k$'s place ($k \geq 0$) of $A \oplus B$, written in binary, is $1$ if exactly one of the digits in the $2^k$'s place of $A$ and $B$, written in binary, is $1$, and $0$ otherwise.

For example, $3 \oplus 5 = 6$ (in binary: $011 \oplus 101 = 110$). In general, the bitwise $\mathrm{XOR}$ of $k$ non-negative integers $p_1, p_2, p_3, \dots, p_k$ is defined as $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$, and it can be proved that this does not depend on the order of $p_1, p_2, p_3, \dots, p_k$.

存在一个长度为 $N$ 的由 $0$ 和 $1$ 构成的序列 $B=(B_1,B_2,\ldots,B_N)$。初始时，$B_1=1$，其余所有元素均为 $0$。

共有 $M$ 个开关，第 $i$ 个开关（$1 \le i \le M$）上写有一个整数 $A_i$。当按下开关 $i$ 时，根据操作前的当前状态，对每个满足 $1 \le j \le N$ 的整数 $j$，同时更新 $B_j$ 如下：

[
B_j \leftarrow \begin{cases} B_j \oplus B_{j-A_i} & (A_i < j),\ B_j & (j \le A_i) \end{cases}
]

每个开关可被按下零次或一次，且开关的按下顺序可以任意。

求最终可能得到的不同序列 $B$ 的个数（对 $998244353$ 取模）。

什么是按位 $\mathrm{XOR}$ 运算？

非负整数 $A$ 与 $B$ 的按位 $\mathrm{XOR}$（记作 $A \oplus B$）定义如下：

• 将 $A \oplus B$ 写成二进制后，其 $2^k$ 位（$k \geq 0$）上的数字为 $1$，当且仅当 $A$ 和 $B$ 的二进制表示中，$2^k$ 位上的数字恰好有一个为 $1$；否则该位为 $0$。

例如，$3 \oplus 5 = 6$（二进制：$011 \oplus 101 = 110$）。一般地，$k$ 个非负整数 $p_1, p_2, p_3, \dots, p_k$ 的按位 $\mathrm{XOR}$ 定义为 $(\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k)$，且可以证明该结果与 $p_1, p_2, p_3, \dots, p_k$ 的运算顺序无关。

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_M$

输入从标准输入中按以下格式给出：

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_M$

Output the number, modulo $998244353$, of possible final sequences $B$.

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

Sample 1 Explanation:
There are four possible final sequences:

• $(1,0,0,0)$
• $(1,0,1,0)$
• $(1,0,0,1)$
• $(1,0,1,1)$

Sample 2 Explanation:
There are two possible final sequences: $(1,0)$ and $(1,1)$.

Constraints

• $2 \le N \le 2 \times 10^5$
• $1 \le M \le 2 \times 10^5$
• $1 \le A_i \lt N$ ($1 \le i \le M$)
• All input values are integers.

样例 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 \lt N$（$1 \le i \le M$）
• 所有输入值均为整数。