从事大型项目的程序员刚刚收到一项任务,要编写恰好 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