Travel in Sugar Country

There are $N$ towns numbered $1$ through $N$. There is a bidirectional road between towns $i$ and $i+1$, and its length is $D\_i$. Thus, for each pairs ($a$, $b$) ($a < b$), the distance between towns $a$ and $b$ is $D(a, b) = D\_a + D\_{a+1} + \ldots + D\_{b-1}$.

At each town there is a sugar shop. An ant wants to visit $K$ distinct shops.

The ant wants to choose a set of $K$ distinct shops and the order to visit them. For example, if it decides to visit the shops $S\_1, \ldots, S\_K$ in this order, the total distance it travels will be $D(S\_1, S\_2) + D(S\_2, S\_3) + \ldots + D(S\_{K-1}, S\_K)$.

In how many ways the total distance it travels become a multiple of $M$? Print the answer modulo $10^9+7$.

$N$ $M$ $K$ 
$D\_1$ 
$D\_2$ 
$\vdots$ 
$D\_{N-1}$

Print the answer modulo $10^9+7$.

•  $2 \leq N \leq 100$ 
•  $1 \leq M \leq 30$ 
•  $2 \leq K \leq 10, K \leq N$ 
•  $1 \leq D\_i \leq M$ 
• All values in the input are integers.

In Sample 1, there are six ways: $1 \rightarrow 3 \rightarrow 2$, $2 \rightarrow 3 \rightarrow 1$, $2 \rightarrow 1 \rightarrow 4$, $4 \rightarrow 1 \rightarrow 2$, $2 \rightarrow 3 \rightarrow 4$, and $4 \rightarrow 3 \rightarrow 2$.