Migrated from Lutece 1692 这是一道比CCCC简单题更有想象力的中档题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在2550年，CCCC已经成为了一场和ICPC一样正式的大型比赛

UESTC在那年派出了一只n个人组成的参赛队参加比赛

2050年的CCCC赛制有了改变，这n个人可以坐在一起讨论问题，一起写代码！

CCCC嘛，前面都是些不着边际的奇怪题目，一直到了最后的终极大BOSS题目

最后大boss的AC代码，将由很多队员一起写成！

已知n个参赛队员，对于第i个队员，每写一行代码，就会留下 $a_i$ 个bug

最后一题需要写m行代码，请安排各个队员写的代码行数（显然要非负），使得整个代码的bug数不超过b个

然后，在ACM玄学之神的保佑下，这份不超过b个bug的代码就能AC了！

问你有多少种不同的安排方案可以写出一份AC代码，要求方案数对mod取模

Input

第一行，n,m,b,mod，1<=n,m<=500,0<=b<=500,1<=mod<=1e9+7

接下来一行n个数，分别是 $a_1$到 $a_n$.

Output

对mod取模之后的方案数

Samples

3 3 3 100
1 1 1

10

Constraints

$0 \leq a_i \leq 500$

Resources

2017 UESTC Training for Dynamic Programming