Background

$\mathbb{S}\mathbb{A}\mathbb{B}\mathbb{R}\mathbb{I}\mathbb{N}\mathbb{A}$ 的团队要组装火箭。

Description

$\mathbb{S}\mathbb{A}\mathbb{B}\mathbb{R}\mathbb{I}\mathbb{N}\mathbb{A}$ 手下有 $N$ 个工人，每个工人都可以加工若干个零件，总共要加工 $K$ 个零件，这 $K$ 个零件可以由多个工人来加工。料事如神的 $\mathbb{S}\mathbb{A}\mathbb{B}\mathbb{R}\mathbb{I}\mathbb{N}\mathbb{A}$ 预测第 $i$ 个工人在加工一个零件的时候会 $a_i$ 个 地方加工不到位。

因为 $\mathbb{S}\mathbb{A}\mathbb{B}\mathbb{R}\mathbb{I}\mathbb{N}\mathbb{A}$ 很懒，所以她希望知道有多少种方案能使得这 $K$ 个零件加工不到位的地方的数量不超过 $Q$ 个。

两个方案不同当且仅当某个工人加工的零件数不同。

Format

Input

第一行包含四个整数 $N,K,Q,P$。

接下来一行 $N$ 个整数 $a_i$。

Output

一行一个整数，表示方案数对 $P$ 取模后的答案。

样例 #1

样例输入 #1

3 5 6 11
1 2 1

样例输出 #1

0

Limitation

对于 100 % 的数据：

$1 \le N,K \le 500$

$0 \le Q \le 500$

$1 \le P \le 10^9+7$

$0 \le a_i \le 500$