У некоторого контеста появилось N спонсоров, причём каждый из них хочет увидеть название своей компании в условиях ровно s_i различных задач. Однако участники этого контеста не хотят видеть в одном и том же условии отсылки более чем к 2-м различным спонсорам.

Жюри, несомненно, могут справиться с такими требованиями, но у них возник вопрос другого рода. Уже известно, что всего задач в контесте будет M, и как они расставлены между собой в комплекте. Теперь в любое из условий можно вписать названия не более двух компаний (например, «DOUBLETAPP» и «X-tensive»). Теперь же стало интересно, сколько способов существует это сделать. Два способа различаются, если у хотя бы одной задачи отличается набор упомянутых спонсоров.

Однако же сейчас жюри занято вписыванием спонсоров в условия, поэтому задача посчитать количество способов это сделать достаётся Вам.

В первой строке даны два целых числа N и M — количество спонсоров у контеста и количество задач в комплекте (1 ≤ N ≤ 1000, 1 ≤ M ≤ 2000).

Во второй строке через пробел даны N целых чисел s_i — пожелания каждого спонсора (1 ≤ s_i ≤ M).

Гарантируется, что суммарное число пожеланий не превосходит 2 · M.

Выведите количество способов вписать названия компаний-спонсоров в комплект по модулю 10⁹+7. То есть, найдите остаток при делении количества способов на 1 000 000 007.

В первом примере существует только четыре способа вписать названия спонсоров: