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