Теофанису действительно нравятся последовательности положительных целых чисел, а потому его учитель (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...]$$$
| Codeforces Round 747 (Div. 2) |
|---|
| Закончено |
