| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 5 | 4 | 4 | 80.000% |
Вернемся немного во времени в события первого фильма, когда корпорация <<Фонд жизни>> проводила эксперименты на людях с участием симбиотов. В итоге все закончилось довольно хорошо, но давайте представим, что было бы, если Эдди с Веномом не остановили бы запуск ракеты, и еще больше симбиотов прибыли бы на Землю.
Прилетевшие 2ドルn$ симбиотов хотят найти себе носителей, и для этого они отобрали 2ドルn$ самых здоровых людей. Известно, что $i$-й симбиот обладает опасностью $a_i,ドル а $i$-й носитель --- вместимостью ровно $B$. Отобранные люди оказались настолько крепкими, что каждый из них может вместить аж до четырех симбиотов одновременно, но только если их суммарная опасность не превышает вместимости носителя.
Чтобы все было честно, был определен следующий порядок объединения с носителями:
Понятно, что симбиоты из первой пары могут выбирать себе носителей только из нее, потому что нулевой пары нет, но каждая следующая пара симбиотов уже имеет выбор между своей парой и предыдущей.
Помогите симбиотам посчитать количество способов, которыми они могут объединиться с носителями. Не обязательно, чтобы каждый носитель в итоге содержал симбиота, но обязательно, чтобы у каждого симбиота был носитель. Поскольку ответ может быть довольно большим, посчитайте его по модулю 10ドル^9 + 7$.
В первой строке ввода через пробел даны два целых числа: $n$ --- количество пар симбиотов (и, соответственно, носителей), и $B$ --- вместимость каждого носителя (1ドル \leqslant n \leqslant 5 \cdot 10^5$; 1ドル \leqslant B \leqslant 10^9$).
Во второй строке через пробел перечислены 2ドルn$ целых чисел $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