CF543A.Writing Code

Programmers working on a large project have just received a task to write exactly m lines of code. There are n programmers working on a project, the i-th of them makes exactly a__i bugs in every line of code that he writes.

Let's call a sequence of non-negative integers _v_1, _v_2, ..., v__n a plan, if _v_1 + _v_2 + ... + v__n = m. The programmers follow the plan like that: in the beginning the first programmer writes the first _v_1 lines of the given task, then the second programmer writes _v_2 more lines of the given task, and so on. In the end, the last programmer writes the remaining lines of the code. Let's call a plan good, if all the written lines of the task contain at most b bugs in total.

Your task is to determine how many distinct good plans are there. As the number of plans can be large, print the remainder of this number modulo given positive integer mod.

正在大型项目上工作的程序员刚刚接到一项任务：恰好编写 $m$ 行代码。项目共有 $n$ 名程序员，其中第 $i$ 位程序员编写的每一行代码中恰好引入 $a_i$ 个错误（bug）。

我们称一个非负整数序列 $v_1,\,v_2,\,\dots,\,v_n$ 为一个方案（plan），若满足 $v_1 + v_2 + \dots + v_n = m$。程序员们按该方案执行任务：首先，第一位程序员编写该任务的前 $v_1$ 行；接着，第二位程序员再编写接下来的 $v_2$ 行；依此类推；最后，第 $n$ 位程序员编写剩余的所有行。我们称一个方案是好的（good），如果整个任务所编写的全部代码行中，引入的错误总数不超过 $b$ 个。

你的任务是计算有多少个互不相同的好的方案。由于方案总数可能非常大，请输出该数目对给定正整数 $mod$ 取模后的余数。

The first line contains four integers n, m, b, mod (1 ≤ n, m ≤ 500, 0 ≤ b ≤ 500; 1 ≤ mod ≤ 109 + 7) — the number of programmers, the number of lines of code in the task, the maximum total number of bugs respectively and the modulo you should use when printing the answer.

The next line contains n space-separated integers _a_1, _a_2, ..., a__n (0 ≤ a__i ≤ 500) — the number of bugs per line for each programmer.

第一行包含四个整数 $n$、$m$、$b$、$mod$（$1 \leq n, m \leq 500$，$0 \leq b \leq 500$；$1 \leq mod \leq 10^9 + 7$）—— 分别表示程序员人数、任务的代码行数、允许的最大总缺陷数，以及输出答案时所用的模数。

下一行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$0 \leq a_i \leq 500$）—— 表示每位程序员每行代码产生的缺陷数。

Print a single integer — the answer to the problem modulo mod.

输出一个整数——该问题答案对 mod 取模的结果。