19528번 - 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$.