|
Поиск сокровищ
(Время: 3 сек. Память: 256 Мб Сложность: 76%)
Для поиска полезных ископаемых ученые разработали специальный сканер.
Представим область для поисков как таблицу из k строк и n столбцов. Нумерация строк идет от 1 до k сверху вниз, нумерация столбцов от 1 до n слева направо. В каждой клетке таблицы могут находиться полезные ископаемые.
Сканер работает следующим образом: он может быть запущен в столбце p и возвращает количество клеток в зоне сканирования, которые содержат полезные ископаемые. Зона сканирования включает все клетки столбца p, верхние k − 1 клетку столбца p − 1, верхние k − 2 клетки столбца p−2, и так далее. На рисунке показана зона сканирования для поля с k = 3, n = 5 и всех значений p.
Вам даны значения, которые вернул сканер для всех p, обозначим за bp значение в столбце p. Будем называть таблицу, где для каждой клетки определено, находятся ли в ней полезные ископаемые, корректной, если для нее сканер возвращает верные значения. Например, если в примере выше сканер вернул значения [2, 1, 2, 3, 2], то одна из корректных таблиц может выглядеть следующим образом (клетки, содержащие ископаемые, обозначены черным треугольником):
По заданным значениям, которые вернул сканер, определите количество корректных таблиц и выведите остаток от деления этого количества на число 109 + 7. Обратите внимание, что, возможно, сканер неисправен, и корректных таблиц вообще нет, тогда необходимо вывести 0.
Входные данные
В первой строке входного файла даны два числа n, k – количество столбцов и строк, соответственно (1 ≤ n ≤ 200, 1 ≤ k ≤ 7). Во второй строке даны n чисел b1, b2, ..., bn – значения, которые вернул сканер (0 ≤ bi ≤ k2).
Выходные данные
В выходной файл OUTPUT.TXT выведите единственное число – остаток от деления количества различных корректных таблиц на 109 + 7.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 3 2 1 2 3 2 | 24 |
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |