Majority and Permutation
给定一个由 1 到 2N−1 之间的奇数组成的序列 (A1,A2,…,AM)。
求满足以下条件的排列 P=(P1,P2,…,P2N)(即 1,2,…,2N 的排列)的个数,对 998244353 取模:
- 存在一个长度为 2N、只含
0 和 1 的字符串 S,满足:
- S 中
0 和 1 各恰有 N 个;
- 对每个 i=1,2,…,M,在 S 的前 Ai 个字符中,出现次数最多的字符是
0;
- 对每个 i=1,2,…,M,在 S 的第 P1,P2,…,PAi 个字符中,出现次数最多的字符是
0。
输入格式
第一行两个整数 N,M(1≤M≤N≤105)。
第二行 M 个整数 A1<A2<⋯<AM(1≤Ai≤2N−1,Ai 为奇数)。
输出格式
输出一个整数,表示满足条件的排列数对 998244353 取模的结果。
样例
输入:
2 2
1 3
输出:
14
例如 P=(2,1,3,4) 时,S=0011 满足全部条件;而 P=(4,3,2,1) 不满足。