Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Поиск сокровищ

(Время: 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.TXTOUTPUT.TXT
15 3
2 1 2 3 2
24

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2006 / 2007
 2007 / 2008
 2008 / 2009
 2009 / 2010
 2010 / 2011
 2011 / 2012
 2012 / 2013
 2013 / 2014
 2014 / 2015
 2015 / 2016
 2016 / 2017
 2017 / 2018
 2018 / 2019
 2019 / 2020
 2020 / 2021
 2021 / 2022
 2022 / 2023
 2023 / 2024
 2024 / 2025
 A. Кузнечик 2D
 B. Простоватые числа
 C. Кислотные дожди
 D. Поиск сокровищ
 E. Разность квадратов
 F. Перекошенное разбиение
 G. Главное правило личных олимпиад
 H. Туристический маршрут

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru