← 返回题目列表

AtCoder · arc156_b

B. 黑板上的墨西哥人

中文机器翻译题面 查看原题

分数: 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 次。

  • 在黑板上选择零个或多个整数。让 S 是所选整数的多重集,并写 \mathrm{mex}(S) 在黑板上一次。

最终黑板上的整数多重集可以有多少个多重集?求这个计数的模数 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

通过运算可以得到以下三个多重集。

  • \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

通过运算可以得到以下两个多重集。

  • \lbrace 0,0,0 \rbrace
  • \lbrace 0,0,1\rbrace

请注意,您可以在运算中选择零个整数。


示例输入 3

5 10
3 1 4 1 5

示例输出 3

7109