B. Особые числа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Теофанису действительно нравятся последовательности положительных целых чисел, а потому его учитель (Yeltsa Kcir) предложил ему задачу про последовательность, которая состоит только из особых чисел.

Назовем положительное число особым, если оно может быть представлено как сумма различных неотрицательных степеней числа $$$n$$$. Например, для $$$n = 4$$$ число $$$17$$$ является особым, так как может быть представлено как $$$4^0 + 4^2 = 1 + 16 = 17$$$, а вот $$$9$$$ не является.

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

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

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

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

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

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

Пример
Входные данные
3
3 4
2 12
105 564
Выходные данные
9
12
3595374
Примечание

При $$$n = 3$$$, последовательность начинается с $$$[1,3,4,9...]$$$