eolymp
bolt
Try our new interface for solving problems
Problems

Ski Race (RU)

Ski Race (RU)

Time limit 6 seconds
Memory limit 64 MiB

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

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

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

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

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

Input data

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

Output data

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

Examples

Input example #1
3 3
2 1 3
Output example #1
2
Author Бирюков С.В.
Source IV Открытая олимпиада ЮФУ