Настольная игра

Недавно Петя подарил Васе замечательную настольную игру. В коробке, среди прочего, находилось множество картонных квадратиков (тайлов), из которых игроки поочерёдно выкладывают игровую карту. На тайлах изображены разные типы объектов — дороги, крепости, рудники и прочее, и их можно разделить на соответствующие группы. Тайлы, относящиеся к одной группе, совершенно одинаковы.

Хотя теоретически плоскость, на которой из тайлов выкладывается карта, бесконечна, на практике она ограничена поверхностью журнального столика Васи. Как по горизонтали, так и по вертикали на этом столике могут поместиться не более M тайлов. Таким образом, Вася и Петя будут выкладывать карту на квадратном поле, изначально содержащем (M^2) пустых клеток. Каждый игрок поочерёдно должен взять следующий случайный тайл и, руководствуясь своими соображениями, поместить его в одну из пустующих клеток. Когда все тайлы выложены, карта считается завершённой (при этом на поле всё ещё могут присутствовать незаполненные клетки).

Мы не будем описывать все правила игры, так как на это вряд ли хватит места в условии. Тем более, Васю в настоящий момент заинтересовала совсем другая вещь. Вася хочет узнать, сколько различных карт можно выложить на журнальном столике, каждый раз используя все имеющиеся тайлы. Две карты считаются различными, если они не могут быть совмещены поворотом столика. Ориентация рисунка на тайлах не имеет значения.

Помогите Васе удовлетворить его любопытство.

Первая строка содержит целые числа N и M (1 <= N <= 50, 1 <= M <= 10^5) — соответственно количество типов тайлов и ширина столика.

Вторая строка содержит N целых чисел K_i (1 <= K_i <= 10^5) — количество тайлов каждого из типов. Общее количество тайлов не превосходит M^2.

Выведите одно целое число — количество различных карт, которые можно составить из тайлов. Так как это число может оказаться очень большим, выведите остаток от его деления на 1000000007.