← 返回题目列表

Codeforces · 543/A

A. 编写代码

中文机器翻译题面 查看原题

从事大型项目的程序员刚刚收到一项任务,要编写恰好 m 行代码。有 n 个程序员在做一个项目,其中第 i 个程序员在他编写的每一行代码中都产生了 ai bug。

让我们将非负整数 v1, v2, ..., vn 的序列称为计划,如果 v1 + v2 + ... + vn = m。程序员遵循这样的计划:一开始,第一个程序员编写给定任务的前 v1 行,然后第二个程序员编写给定任务的 v2 行,依此类推。最后,最后一个程序员编写了剩余的代码行。如果任务的所有书面行总共最多包含 b 个错误,我们就可以称这个计划是好的。

你的任务是确定有多少个不同的好计划。由于计划的数量可能很大,因此在给定正整数模的情况下打印该数字的余数。

输入

第一行包含四个整数 n, m, b, mod (1 ≤ n, m ≤ 500, 0 ≤ b ≤ 500; 1 ≤ mod ≤ 109 + 7) — 程序员的数量、任务中代码的行数、错误的最大总数以及打印答案时应使用的模数。

下一行包含 n 个空格分隔的整数 a1, a2, ..., an (0 ≤ ai ≤ 500) - 每个程序员每行的错误数。

输出

打印一个整数——对 mod 求模的问题的答案。

示例

输入 #1

3 3 3 100
1 1 1

输出 #1

10

输入 #2

3 6 5 1000000007
1 2 3

输出 #2

0

输入 #3

3 5 6 11
1 2 1

输出 #3

0