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