Размещение симбиотов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вернемся немного во времени в события первого фильма, когда корпорация «Фонд жизни» проводила эксперименты на людях с участием симбиотов. В итоге все закончилось довольно хорошо, но давайте представим, что было бы, если Эдди с Веномом не остановили бы запуск ракеты, и еще больше симбиотов прибыли бы на Землю.

Прилетевшие $$$2n$$$ симбиотов хотят найти себе носителей, и для этого они отобрали $$$2n$$$ самых здоровых людей. Известно, что $$$i$$$-й симбиот обладает опасностью $$$a_i$$$, а $$$i$$$-й носитель — вместимостью ровно $$$B$$$. Отобранные люди оказались настолько крепкими, что каждый из них может вместить аж до четырех симбиотов одновременно, но только если их суммарная опасность не превышает вместимости носителя.

Чтобы все было честно, был определен следующий порядок объединения с носителями:

  1. все носители разбиваются на пары, в паре номер $$$i$$$ находятся носители с номерами $$$2i - 1$$$ и $$$2i$$$ (нумерация как носителей, так и пар, с единицы);
  2. аналогичным образом на пары разбиваются все симбиоты;
  3. каждый симбиот из $$$i$$$-й пары может выбрать произвольного носителя из $$$i$$$-й или $$$(i - 1)$$$-й пары (если, конечно, его вместимости для этого хватает).

Понятно, что симбиоты из первой пары могут выбирать себе носителей только из нее, потому что нулевой пары нет, но каждая следующая пара симбиотов уже имеет выбор между своей парой и предыдущей.

Помогите симбиотам посчитать количество способов, которыми они могут объединиться с носителями. Не обязательно, чтобы каждый носитель в итоге содержал симбиота, но обязательно, чтобы у каждого симбиота был носитель. Поскольку ответ может быть довольно большим, посчитайте его по модулю $$$10^9 + 7$$$.

Входные данные

В первой строке ввода через пробел даны два целых числа: $$$n$$$ — количество пар симбиотов (и, соответственно, носителей), и $$$B$$$ — вместимость каждого носителя ($$$1 \leqslant n \leqslant 5 \cdot 10^5$$$; $$$1 \leqslant B \leqslant 10^9$$$).

Во второй строке через пробел перечислены $$$2n$$$ целых чисел $$$a_i$$$ — значения опасности каждого симбиота ($$$1 \leqslant a_i \leqslant 10^9$$$).

Выходные данные

Выведите единственное целое число — количество способов разместить симбиотов по носителям по модулю $$$10^9 + 7$$$. Если нет возможности назначить каждому симбиоту носителя, то число способов равно нулю.

Примеры

Входные данные
2 8
4 5 6 7
Выходные данные
4
Входные данные
2 8
3 4 5 6
Выходные данные
20