时空限制

1S/512M

题目描述

给定四个整数 $n, m, r, k$ 以及一个长度为 $m$ 的整数数组 $w_1, \ldots, w_m$。

你的任务是，统计满足下列所有条件的、长度为 $n$ 的非负整数数组 $(a_1, \ldots, a_n)$ 的数量：

1. 对于数组的前 $m$ 个数（$1 \le i \le m$），每个数 $a_i$ 都有一个上限 $w_i$，即 $0 \le a_i \le w_i$。
2. 数组所有元素的总和为 $k$，即 $\sum_{i=1}^{n} a_i = k$。
3. 在数组的后 $n-m$ 个数中（即 $a_{m+1}, \ldots, a_n$），最多有 $r$ 个数是正整数（大于 $0$）。

由于答案可能很大，请将结果对 $998244353$ 取模。

格式

输入格式

第一行包含四个整数 $n, m, r, k$。具体意义见题目描述

第二行包含 $m$ 个整数 $w_1, w_2, \ldots, w_m$。

输出格式

输出一行，一个整数，表示满足条件的数组数量对 $998244353$ 取模后的结果。

样例

样例输入 #1

3 1 1 5
2

样例输出 #1

6

数据规模

对于 $100\%$ 的数据，$0 \le m \le \min(n, 300)$，$0 \le r \le 300$，$1 \le n, k \le 5 \times 10^6$，$1 \le w_i \le 300$。

子任务 $1$ （$20$ 分）：$n = m$。

子任务 $2$ （$20$ 分）：$m = 0$。

子任务 $4$ （$60$ 分）：无特殊限制。

你必须通过子任务内的所有数据才能获得该子任务的分数。