/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
正整数 N, M, K と長さ K の正整数列 c=(c_1, c_2, \dots, c_K) が与えられます．
M 以下の正整数のみからなる要素数 N の多重集合 S であって，次の条件を全て満たすような K 個の多重集合の組 (S_1, S_2, \dots, S_K) が存在するようなものを良い多重集合と呼びます．
- S_1, S_2, \dots, S_K はいずれも空でない．
- i=1, 2, \dots, K のそれぞれに対して，S_i の中央値は c_i である．
- S_1, S_2, \dots, S_K の要素数の総和は N である．その N 個の要素からなる多重集合は S に等しい．
ただしこの問題において，要素数 n\ (\geq 1) の多重集合 T の中央値とは，T の要素を昇順に並べたときの \lceil n / 2 \rceil 番目の要素であると定義します．例えば， T=\lbrace 1, 2, 3, 4 \rbrace の中央値は 2 であり， T=\lbrace 1, 3, 5, 7, 7 \rbrace の中央値は 5 です．
良い多重集合の個数を 998244353 で割った余りを求めてください．
制約
- 1 \leq N, M \leq 10^7
- 1 \leq K \leq \min(2 \times 10^5, N)
- 1 \leq c_i \leq M
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる．
N \ M \ K c_1 \ c_2 \ \dots \ c_K
出力
良い多重集合の個数を 998244353 で割った余りを出力せよ．
入力例 1
8 5 3 4 1 5
出力例 1
105
例えば S=\lbrace 1,1,1,2,3,4,5,5 \rbrace は，条件を満たす (S_1, S_2, S_3) が次のように存在するため良い多重集合です．
- S_1 = \lbrace 1, \mathbf{4}, 5 \rbrace
- S_2 = \lbrace 1, \mathbf{1}, 2, 3 \rbrace
- S_3 = \lbrace \mathbf{5} \rbrace
入力例 2
10000000 2 2 1 2
出力例 2
9999999
入力例 3
30 10 5 3 1 4 1 5
出力例 3
38446044
Score : 100 points
Problem Statement
You are given positive integers N, M, K, and a sequence of K positive integers c=(c_1, c_2, \dots, c_K).
A multiset S consisting of N positive integers less than or equal to M is called good, if there exists at least one sequence of K multisets (S_1, S_2, \dots, S_K) satisfying the following conditions.
- None of S_1, S_2, \dots, S_K is empty.
- The median of S_i equals to c_i, for all i=1, 2, \dots, K.
- S_1, S_2, \dots, S_K have exactly N elements in total. A multiset consisting of those N elements coincides with S.
Note that we define the median of a multiset T with n\ (\geq 1) elements as the \lceil n / 2 \rceil-th element of T in ascending order. For example, the median of T=\lbrace 1, 2, 3, 4 \rbrace is 2, and that of T=\lbrace 1, 3, 5, 7, 7 \rbrace is 5.
Find the number of good multisets modulo 998244353.
Constraints
- 1 \leq N, M \leq 10^7
- 1 \leq K \leq \min(2 \times 10^5, N)
- 1 \leq c_i \leq M
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N \ M \ K c_1 \ c_2 \ \dots \ c_K
Output
Print the number of good multisets modulo 998244353.
Sample Input 1
8 5 3 4 1 5
Sample Output 1
105
For example, S=\lbrace 1,1,1,2,3,4,5,5 \rbrace is a good multiset because there exists (S_1, S_2, S_3) satisfying the conditions as follows.
- S_1 = \lbrace 1, \mathbf{4}, 5 \rbrace
- S_2 = \lbrace 1, \mathbf{1}, 2, 3 \rbrace
- S_3 = \lbrace \mathbf{5} \rbrace
Sample Input 2
10000000 2 2 1 2
Sample Output 2
9999999
Sample Input 3
30 10 5 3 1 4 1 5
Sample Output 3
38446044