Лыжные гонки
Международная федерация лыжного спорта постоянно работает в направлении повышения зрелищности лыжных гонок. За последние несколько лет было придумано и опробовано множество дисциплин – спринтерские гонки, масстарты, гонки с переобуванием лыж и т.д. Большая часть из них уже была представлена на олимпиаде в Ванкувере. Неотъемлемым эффектом повышения зрелищности является увеличение контактной борьбы непосредственно на трассе, как это происходит в спринте и масстарте. Для таких гонок очень важен момент старта, в частности расположение спортсменов.
К олимпиаде в Сочи решено опробовать новую схему расположения спортсменов на стартовом поле. Как и прежде, лыжники располагаются в несколько колонн, выровненных по стартовой линии. Но теперь количество человек в каждой из колонн определяется регламентом соревнований. Кроме того, лыжники из одной страны не могут:
Находиться в одной колонне.
Находиться в одном ряду, если между ними вся часть ряда занята другими лыжниками (или они находятся в соседних колоннах). Если хотя бы одно место свободно, они могут располагаться в одном ряду.
Федерация лыжного спорта просит вас написать программу, определяющую, сколькими способами можно расставить на старте K спортсменов одной страны?
Входные данные
В первой строке записаны целые числа N и K (1 ≤ N, K ≤ 400). Во второй строке записано N положительных чисел через пробел – описание стартовых колонн. i-ое число указывает количество человек в i-ой колонне. Числа не превышают 1000000.
Выходные данные
Необходимо вывести единственное число – количество способов. Число вывести по модулю 10^9+7.