F. Бесконечная работа
ограничение по времени на тест
2.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Больше обезьян!
— Exponential Idle

Вы руководите масштабным научным проектом по исследованию необычной функции. Для его реализации вы наняли $$$10^{10^{100}}$$$ студентов и пронумеровали их натуральными числами от $$$1$$$ до $$$10^{10^{100}}$$$. Студенты образуют иерархию:

  • Студент $$$1$$$ — самый главный.
  • Для любого $$$i \geq 2$$$ непосредственным начальником студента $$$i$$$ является студент с номером $$$\left\lfloor \frac{i}{2} \right\rfloor$$$.
  • Непосредственными подчинёнными студента $$$i$$$ являются студенты с номерами $$$2i$$$ и $$$2i+1$$$ (если эти числа не превышают $$$10^{10^{100}}$$$).
  • Подчинение транзитивно: если $$$a$$$ подчиняется $$$b$$$, а $$$b$$$ подчиняется $$$c$$$, то $$$a$$$ подчиняется $$$c$$$.
Изначально все студенты работают.

До завершения работы осталось $$$n$$$ дней. Каждый день состоит из двух этапов:

  • Набор. Каждый работающий студент $$$i$$$ набирает всех неработающих студентов, которые непосредственно подчиняются ему:
    • Если студент $$$2i$$$ не работает и $$$2i \leq 10^{10^{100}}$$$, он начинает работать.
    • Если студент $$$2i + 1$$$ не работает и $$$2i + 1 \leq 10^{10^{100}}$$$, он начинает работать.
    Вновь нанятые студенты в этот же день никого нанимать не могут.
  • Увольнение. Вы можете выбрать любое множество работающих студентов и непосредственно уволить каждого из них. При непосредственном увольнении студента $$$i$$$ все его подчинённые также автоматически увольняются. Такие увольнения называются косвенными. Студента $$$1$$$ увольнять нельзя.

Дополнительное ограничение: Каждый студент должен быть уволен (непосредственно или косвенно) не более одного раза. Если уволенный ранее студент будет снова нанят, нельзя производить увольнение, которое приведет к увольнению этого студента.

Ниже (показаны только первые $$$15$$$ студентов) показаны способы выбрать студентов для непосредственного увольнения в каждый из дней так, чтобы после $$$2$$$-х дней осталось ровно $$$5$$$ студентов. Номер на вершине соответствует номеру студента, ребра показывают подчинения между студентами.

Студенты, которые работают и не были уволены помечены зелёным цветом, студенты, которые были уволены помечены белым цветом, а студенты, которые уже были уволены но были наняты повторно — красным.

$$$1$$$-й день, до увольнения. Все студенты наняты. $$$1$$$-й день, после увольнения. Уволены студенты $$$2$$$, $$$6$$$, $$$7$$$ $$$2$$$-й день, до увольнения. Наняты студенты $$$2$$$, $$$6$$$, $$$7$$$. Обратите внимание, что на этапе увольнения $$$3$$$-й студент не может быть непосредственно уволен, так как это приведёт к увольнению $$$6$$$-го и $$$7$$$-го студентов, которые уже были уволены до этого момента.

Ваша цель — сделать так, чтобы ровно через $$$n$$$ дней в проекте осталось ровно $$$k$$$ работающих студентов. При этом необходимо минимизировать суммарное количество непосредственных увольнений за весь период.

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

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

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

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

Для каждого набора входных данных выведите одно целое число — количество возможных способов выбрать увольнения в каждый день так, чтобы после $$$n$$$ дней осталось ровно $$$k$$$ студентов, при условии, что общее количество увольнений минимально возможное.

Пример
Входные данные
6
1 1
2 5
3 4
1 5
20 14
1000000000 20
Выходные данные
1
2
2
42
120
12
Примечание

В первом наборе входных данных $$$1$$$ вариант: в первый день непосредственно уволить студентов с номерами $$$2$$$ и $$$3$$$. Останется ровно один студент с номером $$$1$$$.

Во втором наборе входных данных $$$2$$$ возможных способа:

  • В первый день непосредственно уволить студентов с номерами $$$2$$$, $$$6$$$ и $$$7$$$. Остаются $$$1$$$ и $$$3$$$. В начале второго дня они набирают студентов с номерами $$$2$$$, $$$6$$$ и $$$7$$$.
  • В первый день непосредственно уволить студентов с номерами $$$3$$$, $$$4$$$ и $$$5$$$. Остаются $$$1$$$ и $$$2$$$. В начале второго дня они набирают студентов с номерами $$$3$$$, $$$4$$$ и $$$5$$$.
Можно показать, что нельзя получить в конце $$$5$$$ студентов, уволив меньше трёх студентов.

В третьем наборе входных данных $$$2$$$ возможных способа:

  • В первый день непосредственно уволить $$$3$$$-го студента. Во второй день $$$1$$$-й студент набирает $$$3$$$-го студента. Никого не увольняем. В третий день $$$3$$$-й студент набирает студентов $$$6$$$ и $$$7$$$. После этого непосредственно увольняем $$$2$$$-го студента. Таким образом, остались $$$4$$$ студента: $$$1$$$, $$$3$$$, $$$6$$$ и $$$7$$$.
  • В первый день непосредственно уволить $$$2$$$-го студента. Во второй день $$$1$$$-й студент набирает $$$2$$$-го студента. Никого не увольняем. В третий день $$$2$$$-й студент набирает студентов $$$4$$$ и $$$5$$$. После этого непосредственно увольняем $$$3$$$-го студента. Таким образом, остались $$$4$$$ студента: $$$1$$$, $$$2$$$, $$$4$$$ и $$$5$$$.
Можно показать, что нельзя получить в конце $$$4$$$-х студентов, непосредственно уволив меньше двух студентов.