시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 1 1 1 100.000%

문제

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.

예제 입력 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

힌트

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