题目描述

有 $n$ 个程序员，每个程序员都可以写任意行代码，总共要编写 $m$ 行代码，这 $m$ 行代码可以由多个程序员来编写。但是第 $i$ 个程序员在一行代码中会出现 $a_i$ 个 bug。现在希望知道有多少种方案能使得这 $m$ 行代码中的 bug 的数量不超过 $b$ 个。

两个方案不同当且仅当某个程序员编写的代码量（行数）不同。

输入格式

输入第一行包含四个整数 $n,m,b,mod$，$1\le n,m\le 500$，$0\le b\le 500$，$1\le mod\le 10^9+7$。

接下来一行 $n$ 个整数 $a_i$，$0\le a_i\le 500$。

输出格式

输出一行一个整数，表示 $m$ 行代码 bug 数量不超过 $b$ 的方案数对 $mod$ 取模后的答案。

3 3 3 100
1 1 1

10

3 6 5 1000000007
1 2 3

0

3 5 6 11
1 2 1

0