Das Array ausfüllen
Gegeben ist ein Array mit
n Elementen. Sie wissen, dass alle Werte in diesem Array zwischen 1 und m liegen. Darüber hinaus ist die absolute Differenz zwischen zwei benachbarten Elementen höchstens 1. Einige Werte im Array wurden gelöscht (d. h. durch 0 ersetzt), und Sie sollen ermitteln, auf wie viele verschiedene Arten sich das Array vervollständigen lässt, ohne gegen diese Bedingungen zu verstoßen.Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen
n (1 ≤ n ≤ ) und m (1 ≤ m ≤ 100).Die nächste Zeile besteht aus
n durch Leerzeichen getrennten ganzen Zahlen (1 ≤ ≤ m). Der Wert ist 0, wenn der ursprüngliche Wert an der Stelle i gelöscht wurde.Ausgabe
Das Programm soll die Anzahl der möglichen Arten ausgeben, in denen das Array vollständig ausgefüllt werden kann, ohne die Bedingungen zu verletzen. Da das Ergebnis sehr groß sein kann, wird es modulo ausgegeben.
Beispiele
Eingabe | Ausgabe |
3 5
2 0 2 | 3 |
Erklärung
- 2 1 2
- 2 2 2
- 2 3 2
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB