#P17754. shot

shot

题目描述

在马群中,大马的久久注视着小马.

那快乐的神态,曼妙的身材和矫健的步伐已经深深印在大马的心里.

在长久的犹豫之后,大马决定用自己优秀的射击技巧得到小马的注目.

射击场上有 nn 只气球排成一排,大马会进行 mm 次射击.

为了展现自己的射击技巧,大马每次会请小马选定一个气球 xix_i, 如果第 xix_i 个气球没有被打破, 就会打破第 xix_i 个气球, 否则,大马会随机选择左边或右边第一个没有被打破的气球进行射击(如果一边已经没有气球了,大马一定会射击另一边的气球).

但是,小马的目光并没有投向大马.它在思考:如果大马每次射击都保证击中,最后气球有多少种可能的被打破的状态呢?

大马的心在滴血.它决定请你帮它回答这个问题.

两种状态不同,当且仅当一个气球在一个状态中被打破,在另一个状态中没有被打破.

答案模 998244353998244353 输出.

输入格式

从标准输入读入。

第一行两个整数 n,mn, m.

第二行, mm 个整数, 第 ii 个整数为 xix_i.

输出格式

输出到标准输出。

一行一个整数,表示最终可能的状态数模 998244353998244353.

样例

样例输入 1

6 4
2 3 4 4 

样例输出 1

2

数据范围

设 aia_i 为第 ii 个气球被选中的次数.

对于 20%20\% 的数据, n,m≤20n,m≤20

对于 40%40\% 的数据, n,m≤300n, m ≤ 300

对于 60%60 \% 的数据, n,m≤5000n, m≤ 5000

对于另 10%10\% 的数据, 只存在最多一个整数 ii 满足 ai>1a_i > 1

对于 100%100\% 的数据, 1≤m≤n≤1000000,1≤xi≤n1\le m\le n\le1000000,1\le x_i\le n