有 $N$ 个城镇，编号为 $1$ 到 $N$。城镇 $i$ 和 $i+1$ 之间有一条双向道路，长度为 $D_i$。因此，对于每一对城镇 $(a, b)$（其中 $a < b$），城镇 $a$ 和 $b$ 之间的距离为 $D(a, b) = D_a + D_{a+1} + \dots + D_{b-1}$。

每个城镇都有一家糖果店。一只蚂蚁想要访问 $K$ 个不同的商店。

蚂蚁需要选择 $K$ 个不同的商店并确定访问顺序。例如，如果它决定按 $S_1, \dots, S_K$ 的顺序访问这些商店，那么它走过的总距离为 $D(S_1, S_2) + D(S_2, S_3) + \dots + D(S_{K-1}, S_K)$。

请问有多少种访问方式使得走过的总距离是 $M$ 的倍数？请输出答案对 $10^9 + 7$ 取模的结果。

输入格式

$N \ M \ K$ $D_1$ $D_2$ $\vdots$ $D_{N-1}$

数据范围

• $2 \le N \le 100$
• $1 \le M \le 30$
• $2 \le K \le 10, K \le N$
• $1 \le D_i \le M$
• 输入中的所有值均为整数。

输出格式

输出答案对 $10^9 + 7$ 取模的结果。

样例

样例输入 1

4 4 3
2
1
3

样例输出 1

6

样例输入 2

15 5 10
5
5
5
5
5
5
5
5
5
5
5
5
5
5

样例输出 2

897286330

说明

在样例 1 中，共有 6 种方式：$1 \to 3 \to 2$，$2 \to 3 \to 1$，$2 \to 1 \to 4$，$4 \to 1 \to 2$，$2 \to 3 \to 4$ 以及 $4 \to 3 \to 2$。