在你的帮助下，小青鱼集齐了龙行龘龘之力、文江学海之冠、山渟岳峙之盏、云崖潮生之珠，是时候挑战高高的龙门了。

小青鱼游到龙门之下，突然天像异变，海潮云涌。龙门中有机械运行起来。

安全起见，小青鱼开始调查龙门。小青鱼发现龙门有时会翻转它内部的东西，于是小青鱼打算寻找龙门翻转的规律。

小青鱼准备了很多沙漏，容量为 $M$（$M$ 是正整数）的沙漏的使用规则如下。

1. 沙漏的状态可以用一个 $0\sim M$ 的整数 $x$ 描述（$x$ 代表了沙漏下侧沙子的量）。

2. 每经过 $1$ 单位时间，沙子会流下 $1$ 单位，$x$ 变为 $\min(x+1,M)$ 。

3. 倒置沙漏会使 $x$ 变为 $M-x$（可认为瞬间完成）

同时，根据典籍记载，龙门的翻转是有规律的。具体来说，我们可用一个长为 $n+1$ 的 01 串 $s_{0\sim n}$ 来描述龙门变化的规律。具体地：

• 时刻 $0$ 时，将需要操作的、容量为 $M$ 的沙漏放进龙门。沙漏的初始状态为 $M$。

• 时刻 $i$ 时，若 $s_i=0$，龙门什么也不做。若 $s_i=1$，龙门将沙漏倒置。

• 在时刻 $n$ 的操作完成后，小青鱼会将沙漏拿出，看下沙漏当前的状态。

小青鱼想知道 $s_{0\sim n}$ 是什么。

小青鱼恰好有容量为 $1\sim m$ 的沙漏各一个。小青鱼把所有的沙漏一个一个放进龙门，并记录了结束时沙漏的状态。具体地，在龙门中放入容量为 $i$ 的沙漏，输出值为 $x_i$。

小青鱼尝试反推出 $s_{0\sim n}$，但他发现可能的情况仍然非常多，于是他退而求其次，只想计算 $s_{0\sim n}$ 取值方案数对 $998244353$ 取模的结果。你能帮小青鱼解决这个问题吗？

输入格式

第一行一共两个正整数 $n, m$。

第二行一行 $m$ 个数，第 $i$ 个数 $x_i$ 龙门接受大小为 $i$ 的沙漏时的输出值。

输出格式

输出一行一个整数，表示 $s_{0\sim n}$ 取值方案数对 $998244353$ 取模的结果。

样例一

input

3 3
1 1 1

output

2

explanation

样例一中，两种可行的 $s_{0\sim 3}$ 方案如下：

• $s=\texttt{0010}$
• $s=\texttt{1110}$

样例二

input

10 6
1 2 3 3 3 4

output

8

样例三

input

16 16
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

output

12871

样例四

见下发文件。

限制与约定

对于所有的数据，保证 $1 \leq n, m\leq 2.5\times10^5,\ 0\leq x_i\leq i$，至少存在一种符合题意的方案。

时间限制：$1\texttt{s}$

空间限制：$512\texttt{MB}$