Problem Description

The Sweet Country is a very long and narrow country. There are $ N $ towns in the Sweet Country, which are lined up in a straight line, numbered from $ 1 $ to $ N $ in order from one end. There are roads between adjacent towns, and the length of the road connecting town $ i $ and town $ i+1 $ is $ D_i $. The only means of transportation in the Sweet Country are these roads, so the distance to travel from town $ a $ to town $ b $ ($ a < b $) and from town $ b $ to town $ a $ is both $ D_a + D_{a+1} + ... + D_{b-1} $. Each town has a sugar specialty store, and each store sells one type of sugar unique to that town. When visiting a town, you must buy the sugar sold at that town's specialty store.

Ant, who lives in the Ant Kingdom, loves sweet things and the number $ M $. Ant wants to travel to the Sweet Country to buy exactly $ K $ types of sugar. To decide the order in which to visit the towns, Ant first wants to calculate how many ways there are to visit the towns such that the total travel distance is a multiple of $ M $. Note that travel between towns does not involve detours. The first and last towns visited can be any town. You cannot visit the same town twice, and passing through a town during travel between towns does not count as visiting that town.

Please write a program to help Ant find the number of ways to visit the towns in the Sweet Country such that the total travel distance is a multiple of $ M $. Since the answer can be a very large number, output the answer modulo $ 1000000007(10^9+7) $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ D_1 $ $ D_2 $ : $ D_{N-1} $

• The first line contains the integer $N\ (2 ≦ N ≦ 100)$ representing the number of towns in the Sweet Country, the integer $M\ (1 ≦ M ≦ 30)$ representing Ant's favorite number, and the integer $K\ (2 ≦ K ≦ 10$ and $ K ≦ N) $ representing the number of sugar types Ant wants to buy, all separated by spaces.
• The next $ N-1 $ lines contain the lengths of the roads between adjacent towns. The $ i $-th line contains the integer $D_i\ (1 ≦ D_i ≦ M)$ representing the length of the road connecting town $ i $ and town $ i+1 $.

Output Format

Output the answer modulo $ 1000000007(10^9+7) $ on a single line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

4 4 3
2
1
3

Sample Output #1

6

Sample Input #2

15 5 10
5
5
5
5
5
5
5
5
5
5
5
5
5
5

Sample Output #2

897286330

Notes/Hints

Partial Points

This problem has partial points.

• If you correctly solve all test cases where $ N ≦ 12 $, you will be awarded $ 30 $ points.

Sample Explanation 1

There are $ 6 $ ways to visit the towns:
- Town $ 1 $ → Town $ 3 $ → Town $ 2 $
- Town $ 2 $ → Town $ 3 $ → Town $ 1 $
- Town $ 2 $ → Town $ 1 $ → Town $ 4 $
- Town $ 4 $ → Town $ 1 $ → Town $ 2 $
- Town $ 2 $ → Town $ 3 $ → Town $ 4 $
- Town $ 4 $ → Town $ 3 $ → Town $ 2 $

Sample Explanation 2

The answer can be a very large number, so remember to calculate the answer modulo $ 1000000007(10^9+7) $.

见题面 Input 部分

见题面 Output 部分