Riempimento dell'array
Dato un array di
n elementi, si sa che tutti i valori nell’array sono compresi tra 1 e m. Inoltre, la differenza assoluta tra due elementi adiacenti è al massimo 1. Alcuni valori nell’array sono stati cancellati e l’obiettivo è calcolare in quanti modi diversi è possibile riempire l’array senza violare queste condizioni.Input
La prima riga di input contiene due interi
n (1 ≤ n ≤ ) e m (1 ≤ m ≤ 100).La riga successiva contiene
n interi separati da spazi (1 ≤ ≤ m), che rappresentano gli elementi dell’array. Se il valore di è 0, significa che il valore originale in quella posizione è stato cancellato.Output
Il programma deve stampare il numero di modi possibili per riempire l’array rispettando le condizioni indicate. Poiché il risultato può essere molto grande, va stampato modulo .
Esempi
Input | Output |
3 5
2 0 2 | 3 |
Spiegazione
- 2 1 2
- 2 2 2
- 2 3 2
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB