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