ciudades están situadas en una línea en el orden 1, 2, \ldots, n, y la distancia entre las ciudades e i+1 es igual a D_i para cada desde hasta n-1.
Debes contar la cantidad de rutas que cumplen las siguientes condiciones:
La ruta contiene exactamente ciudades
Todas las ciudades de la ruta son distintas dos a dos
La longitud total de la ruta es divisible entre .
La longitud total de una ruta es igual a la suma de las distancias entre ciudades consecutivas de la ruta. La distancia entre las ciudades se define mediante la siguiente fórmula:
D_i + \ldots + D_{j - 1}, si i < j.
D_j + \ldots + D_{i - 1}, si j < i.
Por ejemplo, si n = 4 y D = [3, 5, 7], entonces la longitud de la ruta [3, 1, 4] es igual a 8 + 15 = 23.
Imprime la cantidad de rutas módulo 10^9+7.
La primera línea contiene tres números enteros n, m, k (2 \le n \le 80, 1 \le m \le 80, 2 \le k \le n) — la cantidad de ciudades en la línea, el número entre el cual debe ser divisible la longitud total de la ruta y la cantidad de ciudades de la ruta.
La siguiente línea contiene n - 1 números enteros D_1, D_2, \ldots, D_{n-1} (1 \le D_i \le m) — las distancias entre ciudades vecinas.
Imprime la cantidad de rutas módulo 10^9+7.
Ejemplo 1
Ejemplo 2
En el primer ejemplo existen rutas de este tipo:
2 \to 3 \to 4: la longitud es igual a 2+3 = 5.
4 \to 3 \to 2: la longitud es igual a 3+2 = 5.
1 \to 3 \to 2: la longitud es igual a (1+2)+2 = 5.
2 \to 3 \to 1: la longitud es igual a 2+(1+2) = 5.