题目描述

在“算法魔法”的结业考试上，小明需要完成一项终极挑战。挑战围绕着一个名为 $mex$ 的核心概念。

对于一个可重集的非负整数 $S$，其 $mex(S)$ 值被定义为不在 $S$ 中的最小非负整数。

黑板上初始有 $N$ 个非负整数。你需要执行恰好 $K$ 次迭代操作。在第 $i$ 次操作时：

• 从当前黑板上已有的所有数字中，任选一个子集 $S$，计算 $v=mex(S)$。
• 将数字 $v$ 添加到黑板上。这个新加入的数字将立即生效，可用于后续的操作中（例如，在第 $i+1$ 次操作时，它可以被选入子集 $S$）。

所有 $K$ 次操作添加的数字，它们的总和不得超过总预算 $W$。请计算，总共有多少种不同的添加序列，可以满足预算限制？

一个添加序列指的是 $K$ 次操作中，按顺序添加的 $K$ 个数字。例如，当 $K=2$ 时，序列 $(0, 1)$ 和 $(1, 0)$ 是两种不同的序列。

答案需要对 $998244353$ 取模。

输入格式

第一行包含三个整数 $N,K,W$。

第二行包含 $N$ 个整数 $A_1,A_2,\dots,A_N$。

输出格式

输出一个整数，表示满足条件的添加序列的总数，对 $998244353$ 取模。

2 2 2 
0 2

4

解释 #1

可能的序列为 $(0,0), (0,1), (1,0), (1,1)$，共 4 种。

数据范围

子任务 1（20 分）：$1≤K≤8, 1≤N≤50，0≤W,A_i​≤50。$

子任务 2（30 分）：$1≤K,W≤200, 1≤N≤2×10^5。$

子任务 3（50 分）: $1≤K,W,N,A_i​≤2×10^5,K×W≤1.5×10^5$