cities are located on a line in the order 1, 2, \ldots, n, and the distance between cities and i+1 equals D_i for every from to n-1.
You need to count the number of routes satisfying the following conditions:
The route contains exactly cities
All cities in the route are pairwise distinct
The total length of the route is divisible by .
The total length of a route equals the sum of the distances between consecutive cities of the route. The distance between cities is defined by the following formula:
D_i + \ldots + D_{j - 1}, if i < j.
D_j + \ldots + D_{i - 1}, if j < i.
For example, if n = 4 and D = [3, 5, 7], then the length of the route [3, 1, 4] equals 8 + 15 = 23.
Print the number of routes modulo 10^9+7.
The first line contains three integers n, m, k (2 \le n \le 80, 1 \le m \le 80, 2 \le k \le n) — the number of cities on the line, the number the total length of the route must be divisible by, and the number of cities in the route.
The next line contains n - 1 integers D_1, D_2, \ldots, D_{n-1} (1 \le D_i \le m) — the distances between neighbouring cities.
Print the number of routes modulo 10^9+7.
Example 1
Example 2
In the first sample there are such routes:
2 \to 3 \to 4: the length equals 2+3 = 5.
4 \to 3 \to 2: the length equals 3+2 = 5.
1 \to 3 \to 2: the length equals (1+2)+2 = 5.
2 \to 3 \to 1: the length equals 2+(1+2) = 5.