eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Лыжные гонки

Лыжные гонки

Лимит времени 6 секунд
Лимит использования памяти 64 MiB

Международная федерация лыжного спорта постоянно работает в направлении повышения зрелищности лыжных гонок. За последние несколько лет было придумано и опробовано множество дисциплин – спринтерские гонки, масстарты, гонки с переобуванием лыж и т.д. Большая часть из них уже была представлена на олимпиаде в Ванкувере. Неотъемлемым эффектом повышения зрелищности является увеличение контактной борьбы непосредственно на трассе, как это происходит в спринте и масстарте. Для таких гонок очень важен момент старта, в частности расположение спортсменов.

К олимпиаде в Сочи решено опробовать новую схему расположения спортсменов на стартовом поле. Как и прежде, лыжники располагаются в несколько колонн, выровненных по стартовой линии. Но теперь количество человек в каждой из колонн определяется регламентом соревнований. Кроме того, лыжники из одной страны не могут:

  • Находиться в одной колонне.

  • Находиться в одном ряду, если между ними вся часть ряда занята другими лыжниками (или они находятся в соседних колоннах). Если хотя бы одно место свободно, они могут располагаться в одном ряду.

Федерация лыжного спорта просит вас написать программу, определяющую, сколькими способами можно расставить на старте K спортсменов одной страны?

Входные данные

В первой строке записаны целые числа N и K (1N, K400). Во второй строке записано N положительных чисел через пробел – описание стартовых колонн. i-ое число указывает количество человек в i-ой колонне. Числа не превышают 1000000.

Выходные данные

Необходимо вывести единственное число – количество способов. Число вывести по модулю 10^9+7.

Пример

Входные данные #1
3 3
2 1 3
Выходные данные #1
2
Автор Бирюков С.В.
Источник IV Открытая олимпиада ЮФУ