/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
有限個の非負整数からなる多重集合 S にたいして、\mathrm{mex}(S) を、S に含まれない最小の非負整数と定義します。例えば、\mathrm{mex}(\lbrace 0,0, 1,3\rbrace ) = 2, \mathrm{mex}(\lbrace 1 \rbrace) = 0, \mathrm{mex}(\lbrace \rbrace) = 0 です。
黒板に N 個の非負整数が書かれており、i 番目の非負整数は A_i です。
あなたは、以下の操作をちょうど K 回行います。
- 黒板に書かれている非負整数を 0 個以上選ぶ。選んだ非負整数からなる多重集合を S として、\mathrm{mex}(S) を黒板に 1 個書き込む。
最終的に黒板に書かれている非負整数の多重集合としてありうるものの個数を 998244353 で割ったあまりを求めてください。
制約
- 1 \leq N,K \leq 2\times 10^5
- 0\leq A_i\leq 2\times 10^5
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
3 1 0 1 3
出力例 1
3
操作後に得られる多重集合は、以下の 3 通りです。
- \lbrace 0,0,1,3 \rbrace
- \lbrace 0,1,1,3\rbrace
- \lbrace 0,1,2,3 \rbrace
例えば、\lbrace 0,1,1,3\rbrace は黒板に書かれている 0 を選び、S=\lbrace 0\rbrace として操作をすることで得られます。
入力例 2
2 1 0 0
出力例 2
2
操作後に得られる多重集合は、以下の 2 通りです。
- \lbrace 0,0,0 \rbrace
- \lbrace 0,0,1\rbrace
操作で選ぶ整数は 0 個でも良いことに注意してください。
入力例 3
5 10 3 1 4 1 5
出力例 3
7109
Score : 500 points
Problem Statement
For a finite multiset S of non-negative integers, let us define \mathrm{mex}(S) as the smallest non-negative integer not in S. For instance, \mathrm{mex}(\lbrace 0,0, 1,3\rbrace ) = 2, \mathrm{mex}(\lbrace 1 \rbrace) = 0, \mathrm{mex}(\lbrace \rbrace) = 0.
There are N non-negative integers on a blackboard. The i-th integer is A_i.
You will perform the following operation exactly K times.
- Choose zero or more integers on the blackboard. Let S be the multiset of chosen integers, and write \mathrm{mex}(S) on the blackboard once.
How many multisets can be the multiset of integers on the final blackboard? Find this count modulo 998244353.
Constraints
- 1 \leq N,K \leq 2\times 10^5
- 0\leq A_i\leq 2\times 10^5
- All numbers in the input are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Print the answer.
Sample Input 1
3 1 0 1 3
Sample Output 1
3
The following three multisets can be obtained by the operations.
- \lbrace 0,0,1,3 \rbrace
- \lbrace 0,1,1,3\rbrace
- \lbrace 0,1,2,3 \rbrace
For instance, you can get \lbrace 0,1,1,3\rbrace by choosing the 0 on the blackboard to let S=\lbrace 0\rbrace in the operation.
Sample Input 2
2 1 0 0
Sample Output 2
2
The following two multisets can be obtained by the operations.
- \lbrace 0,0,0 \rbrace
- \lbrace 0,0,1\rbrace
Note that you may choose zero integers in the operation.
Sample Input 3
5 10 3 1 4 1 5
Sample Output 3
7109