UOJ Logo Universal Online Judge

UOJ

#842. 龙门奇械

附件下载 统计

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

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

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

小青鱼准备了很多沙漏,容量为 $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$,至少存在一种符合题意的方案。

子任务编号 $n\leq$ $m\leq$ 特殊性质 分值
$1$ $16$ $16$ $8$
$2$ $2.5\times 10^5$ $6$ $15$
$3$ $1000$ $300$ $37$
$4$ $5\times 10^4$ $5\times 10^4$ $17$
$5$ $2.5\times 10^5$ $2.5\times 10^5$ 所有 $x_i=0$ $10$
$6$ $2.5\times 10^5$ $2.5\times 10^5$ $13$

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

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