Rellenando el arreglo
Dado un arreglo de n elementos, se sabe que todos los valores del arreglo están entre 1 y m. Además, la diferencia absoluta entre dos elementos adyacentes es como máximo 1. Algunos valores se han borrado del arreglo, y se solicita calcular la cantidad de maneras de llenar el arreglo sin violar estas condiciones.
Entrada
La primera línea de la entrada contiene dos enteros n (1 ≤ n ≤ ) y m (1 ≤ m ≤ 100).
La siguiente línea contiene n enteros separados por espacios, (1 ≤ ≤ m) que representan los elementos del arreglo. El valor de igual a 0 indica el valor borrado en la posición i.
Salida
El programa debe imprimir el número de formas de llenar el arreglo que cumplan las condiciones. Debido a que el resultado puede ser muy grande, se deberá imprimir el resultado tomado módulo .
Ejemplos
Entrada | Salida |
|---|---|
3 5 2 0 2 | 3 |
Explicación
2 1 2
2 2 2
2 3 2
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB