J. Выгляни в окно
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Дианы скоро день рождения! Как и полагается математикам, Диана любит прямоугольники, поэтому друзья обещали подарить ей прямоугольную доску. Размеры доски Диана не знает, но она назвала $$$t$$$ возможных вариантов, $$$i$$$-й из которых представляет собой доску $$$a_i \times b_i$$$ клеток. Подаренную доску нельзя поворачивать.

Диана уже придумала, что будет делать с подарком: она собирается вырезать в доске окно. Диана решила, что окно должно иметь площадь ровно $$$s$$$ (состоять из $$$s$$$ клеток). Диана очень любит прямоугольники! Поэтому окно тоже должно иметь форму прямоугольника, длины сторон которого целые числа. Кроме того, окно не должно затрагивать границу подаренной доски, то есть всегда должна оставаться хотя бы одна клетка слева, сверху, справа и снизу от окна. Примеры корректного расположения окна из $$$4$$$ клеток на доске $$$5\times 6$$$:

А следующие расположения являются некорректными:

Для каждого из $$$t$$$ вариантов подарка вам необходимо посчитать, сколько существует способов расположить внутри доски окно площадью $$$s$$$. Два способа считаются различными, если отличаются размеры вырезанного окна или расположение окна внутри доски (иными словами, отличаются множества вырезанных клеток). Поскольку ответ может быть очень большим, нужно вывести лишь его остаток от деления на $$$10^9+7$$$.

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

Первая строка содержит два натуральных числа — $$$t$$$ и $$$s$$$ — количество возможных досок и желаемая площадь окна ($$$1 \leq t \leq 2\cdot 10^5$$$, $$$1 \leq s \leq 10^{15}$$$).

Каждая из следующих $$$t$$$ строк содержит два целых числа — $$$a_i$$$ и $$$b_i$$$ — размеры очередной доски ($$$1 \leq a_i, b_i \leq 10^9$$$).

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

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

Примеры
Входные данные
3 4
5 6
5 5
6 5
Выходные данные
9
4
9
Входные данные
2 1
2 2
3 3
Выходные данные
0
1
Примечание

Несколько примеров корректного расположения прямоугольника из $$$4$$$ клеток на доске $$$5\times 6$$$ приведены в условии. Всего таких вариантов — $$$9$$$, как и для доски $$$6\times 5$$$. На доске $$$5\times 5$$$ можно корректно расположить только прямоугольное окно размера $$$2\times 2$$$ — таких вариантов $$$4$$$.

Во втором примере окно нельзя расположить в прямоугольнике $$$2\times 2$$$, оно всегда будет задевать границу. В прямоугольнике $$$3\times 3$$$ есть только один вариант расположения — центральная клетка.