题目描述

在一个大型项目中工作的程序员们刚刚收到一个任务，要求他们编写正好 $m$ 行代码。

项目中有 $n$ 名程序员，其中第 $i$ 名程序员在每行代码中都会产生恰好 $a_i$ 个错误。

我们称一组非负整数 $v_1, v_2, \ldots, v_n$ 为一个 计划，如果 $v_1 + v_2 + \ldots + v_n = m$。

程序员们按照这样的计划进行工作：一开始，第一个程序员编写前 $v_1$ 行任务代码，然后第二个程序员再编写 $v_2$ 行任务代码，……，依此类推。最后，最后一名程序员编写剩余的 $v_n$ 行代码。如果所有编写的任务行总共包含至多 $b$ 个错误（即 $\sum\limits_{i=1}^n \{ v_i \cdot a_i \} \le b$），我们称这个计划是一个好的计划。

你的任务是确定有多少个不同的好的计划。由于计划的数量可能很大，请输出这个数字对给定的正整数 $mod$ 取模后的结果。

输入格式

第一行包含四个整数 $n, m, b, mod$（$1 \le n,m \le 500$，$0 \le b \le 500$；$1 \le mod \le 10^9+7$）分别表示程序员的数量、任务中的代码行数、最大错误总数以及在输出答案时应使用的模数。

下一行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \ldots, a_n$ （$0 \le a_i \le 500$），表示每个程序员每行代码的错误数量。

输出格式

输出一个整数，表示好的计划的数量对 $mod$ 取模后的结果。

样例

3 3 3 100
1 1 1

10

3 6 5 1000000007
1 2 3

0

5 10 20 10007
1 2 3 4 5

94