#P18150. Majority and Permutation

Majority and Permutation

Majority and Permutation

给定一个由 11 到 2N−12N-1 之间的奇数组成的序列 (A1,A2,…,AM)(A_1,A_2,\dots,A_M)。

求满足以下条件的排列 P=(P1,P2,…,P2N)P=(P_1,P_2,\dots,P_{2N})(即 1,2,…,2N1,2,\dots,2N 的排列)的个数,对 998244353998244353 取模:

  • 存在一个长度为 2N2N、只含 0 和 1 的字符串 SS,满足:
    • SS 中 0 和 1 各恰有 NN 个;
    • 对每个 i=1,2,…,Mi=1,2,\dots,M,在 SS 的前 AiA_i 个字符中,出现次数最多的字符是 0;
    • 对每个 i=1,2,…,Mi=1,2,\dots,M,在 SS 的第 P1,P2,…,PAiP_1,P_2,\dots,P_{A_i} 个字符中,出现次数最多的字符是 0。

输入格式

第一行两个整数 N,MN,M(1≤M≤N≤1051\le M\le N\le 10^5)。

第二行 MM 个整数 A1<A2<⋯<AMA_1<A_2<\dots<A_M(1≤Ai≤2N−11\le A_i\le 2N-1,AiA_i 为奇数)。

输出格式

输出一个整数,表示满足条件的排列数对 998244353998244353 取模的结果。

样例

输入:

2 2
1 3

输出:

14

例如 P=(2,1,3,4)P=(2,1,3,4) 时,S=0011S=0011 满足全部条件;而 P=(4,3,2,1)P=(4,3,2,1) 不满足。