Заполнение массива
Дан массив из
n элементов. Известно, что все значения массива лежат в диапазоне от 1 до m. Кроме того, абсолютная разница между двумя соседними элементами не превышает 1. Некоторые значения в массиве были стёрты, и требуется определить, сколькими различными способами можно восстановить эти стёртые элементы, не нарушив заданные условия.Входные данные
В первой строке входа указаны два целых числа
n (1 ≤ n ≤ ) и m (1 ≤ m ≤ 100).Во второй строке содержатся
n целых чисел (1 ≤ ≤ m), разделённых пробелами, которые представляют элементы массива. Значение равно 0, если элемент в позиции i был стёрт.Выходные данные
Нужно вывести количество способов заполнить массив так, чтобы все условия были выполнены. Поскольку результат может быть очень большим, его следует выводить по модулю .
Примеры
Input | Output |
3 5
2 0 2 | 3 |
Пояснение
- 2 1 2
- 2 2 2
- 2 3 2
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB