Лижні гонки#741
Міжнародна федерація лижного спорту постійно працює над підвищенням привабливості лижних гонок. Останніми роками створюються й випробовуються різноманітні дисципліни — спринти, мас-старти, естафети на зміну лиж тощо. Багато з них уже були представлені на Олімпіаді у Ванкувері. Важливим аспектом підвищення видовищності є посилення безпосередньої боротьби на трасі, як це відбувається у спринтах і мас-стартах. Для таких змагань особливо важливою є організація старту, а особливо — розташування спортсменів.
На майбутній зимовій Олімпіаді запропоновано нову схему розміщення спортсменів на стартовому полі. Як і раніше, лижників розташовують у кілька колон уздовж стартової лінії. Тепер, однак, кількість учасників у кожній колоні визначає регламент змагань. Додатково до цього лижники з однієї країни підпорядковуються таким обмеженням:
Вони не можуть бути розміщені в одній і тій самій колоні.
Вони не можуть бути розміщені в одному й тому самому ряду, якщо всі місця між ними в цьому ряду зайняті іншими лижниками (або якщо вони розташовані в сусідніх колонках). Якщо між ними бодай одне місце порожнє, їх можна розміщувати в одному ряду.
Федерація просить вас написати програму, яка визначить, скількома способами можна розташувати на старті спортсменів з однієї країни.
У першому рядку задано цілі числа і (1 \leq N, K \leq 400). У другому рядку йдуть додатних цілих чисел, розділених пробілами, які описують стартові колонки. -те число означає кількість місць у -ій колонці. Числа не перевищують .
Виведіть одне число — кількість способів. Відповідь виведіть по модулю 10^9+7.
Приклад 1