Problem Statement

Ganmo the kangaroo is trying to cross a row of rocks from one end to the other by jumping.

There are $WK+1$ rocks placed at equal intervals in a row, numbered $0, 1, 2, \cdots\ , WK$ from left to right. All rocks whose numbers are multiples of $W$ are white. Ganmo has currently landed on rock $0$ and wants to cross to rock $WK$.

From the rock he is currently on, Ganmo can move to a rock whose number is larger by $A_1, A_2, \cdots, A_N$. That is, when he is on rock $i$, he can choose any integer $1\le j \le N$, jump, and land on rock $i+A_j$. He cannot jump toward a smaller number.

However, Ganmo has decided not to jump over $2$ white rocks in a row. That is, for every integer $0\le i \lt K$, if he does not land on rock $iW$, he must land on rock $(i+1)W$.

Find the number of ways to jump from rock $0$ to rock $WK$ in the manner described above, modulo $10^9+7$. Two ways of jumping are considered different if there exists a rock that is landed on in one way but not in the other.

Input

$N\ W\ K$
$A_1\ A_2\ \cdots\ A_N$

The input satisfies the following constraints.

• All inputs are integers
• $1 \le W \le 40$
• $1 \le N \le 2W$
• $1 \le A_i \le 2W$
• If $i\ne j$, then $A_i \ne A_j$
• $1 \le K \le 10^{18}$

Output

Output the number of ways to jump modulo $10^9+7$, followed by a newline.

Sample

2 4 1
1 2

5

2 5 1
1 2

8

5 40 31415926535
2 3 5 7 11

320973216