El camino a casa#12852

El camino a casa

8 segundos
256 megabytes
Muy difícil

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

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.

Entrada

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.

Salida

Imprime la cantidad de rutas módulo 10^9+7.

Ejemplos

Ejemplo 1

Loading
Loading

Ejemplo 2

Loading
Loading

Nota

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.