背景

本题疑似错题，在目前的数据范围约束下，已知不存在时间复杂度低于 $O(N^2\log N)$ 的做法，更不用谈通过本题的做法。如果蓝桥杯赛后增加了额外的数据范围约束，本题将另做调整。

题目描述

小蓝的学校正在组织一年一度的运动会。本次运动会共有 $N$ 个班级参赛，其中第 $i$ 个班级报名了 $a_i$ 名学生。

为了保证比赛的公平性与观赏性，组委会决定从所有报名的学生中，选拔出 $M$ 名学生正式参加比赛。同时，为了避免某个班级人数过多，组委会规定：来自同一个班级的参赛人数不能超过 $K$ 个人。

现在，请你帮小蓝计算一下，一共有多少种选拔参赛学生的方案？两种选拔方案被视为不同，当且仅当至少有一名被选中的学生不同。由于方案数可能很大，请将结果对 $998244353$ 取模后输出。

输入格式

第一行包含三个正整数 $N, M, K$，分别表示班级数、需要选拔的总人数，以及每个班级最多入选人数。

第二行包含 $N$ 个正整数 $a_1, a_2, \dots, a_N$，表示每个班级的报名人数。

输出格式

输出一行，一个整数，表示合法选拔方案数对 $998244353$ 取模后的结果。

3 4 2
2 3 2

31

提示

【样例说明】

三个班级分别报名 $2, 3, 2$ 人，共有 $7$ 名学生。若没有每班最多 $2$ 人的限制，从 $7$ 人中选 $4$ 人共有 $\binom{7}{4} = 35$ 种方案。

唯一不合法的情况是第 $2$ 个班级的 $3$ 人全部被选中。此时还需要从第 $1$ 个和第 $3$ 个班级的共 $4$ 名学生中选出 $1$ 人，共 $4$ 种不合法方案。

因此合法方案数为 $35 - 4 = 31$。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le N, M, K, a_i \le 20$。

对于 $80\%$ 的评测用例，$1 \le N, M, K, a_i \le 500$。

对于所有评测用例，$1 \le N, M, K, a_i \le 50000$，且 $M \le \sum_{i=1}^N a_i$。