You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 C 喜欢骰子，尽管这些骰子非常奇怪。

小 C 的手中有 $n$ 个不同的骰子，其中第 $i$ 个骰子是 $a_i$ 面骰子，每个面上的数字依次为 $1,2,3,\cdots,a_i$。

现在，小 C 要选择其中的 $k$ 个骰子，并对于这 $k$ 个骰子中的每一个骰子，选择一个面朝上。

小 C 想要知道，共有多少种不同的选择骰子和选择朝上的面的方案，可以使所有选择的骰子的朝上的面上的数字之和不大于 $p$。

两种选择骰子和选择朝上的面的方案不同，当且仅当存在一个只在其中一种选择方案中出现的骰子或存在一个同时出现在这两种选择方案的骰子的朝上的面上的数字不同。

由于答案可能很大，所以你只需要输出答案对 $998244353$ 取模的结果。

输入格式

第一行三个整数 $n,k,p$。

第二行 $n$ 个整数，表示数组 $a$。

输出格式

一行一个整数，表示满足条件的不同的选择骰子和选择朝上的面的方案数对 $998244353$ 取模的结果。

样例 #1

样例输入 #1

3 2 5
3 4 6

样例输出 #1

28

样例 #2

样例输入 #2

4 4 13
6 4 5 3

样例输出 #2

296

提示

【样例 #3】

见附加文件中的 dice/dice3.in 与 dice/dice3.ans。

该样例满足测试点 $8$ 的限制。

【样例 #4】

见附加文件中的 dice/dice4.in 与 dice/dice4.ans。

该样例满足测试点 $11$ 的限制。

【样例 #5】

见附加文件中的 dice/dice5.in 与 dice/dice5.ans。

该样例满足测试点 $13$ 的限制。

【样例 #6】

见附加文件中的 dice/dice6.in 与 dice/dice6.ans。

该样例满足测试点 $20$ 的限制。

【数据范围】

对于 $100\%$ 的数据，$1 \le k \le n \le 200$，$1 \le p \le 1000$，$1 \le a_i \le 10^9$。

特殊性质：保证 $k=n$。