The Way Home#12852

The Way Home

8 seconds
256 megabytes
Very hard

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 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:

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.

Input

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.

Output

Print the number of routes modulo 10^9+7.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

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.