Preenchendo o array
Dado um array de
n elementos, sabe-se que todos os valores no array estão entre 1 e m. Além disso, a diferença absoluta entre dois elementos adjacentes é, no máximo, 1. Alguns valores do array foram apagados, e o problema consiste em calcular quantas maneiras diferentes existem de preencher o array sem violar estas condições.Entrada
A primeira linha da entrada contém dois inteiros
n (1 ≤ n ≤ ) e m (1 ≤ m ≤ 100).A linha seguinte contém
n inteiros separados por espaço (1 ≤ ≤ m) que representam os elementos do array. Se for 0, isso indica que o valor na posição i foi apagado.Saída
O programa deve imprimir o número de maneiras de preencher o array que respeitam as condições. Como o resultado pode ser grande, a resposta deve ser apresentada módulo .
Exemplos
Entrada | Saída |
3 5
2 0 2 | 3 |
Explicação
- 2 1 2
- 2 2 2
- 2 3 2
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB