Теофанису действительно нравятся последовательности положительных целых чисел, а потому его учитель (Yeltsa Kcir) предложил ему задачу про последовательность, которая состоит только из особых чисел.
Назовем положительное число особым, если оно может быть представлено как сумма различных неотрицательных степеней числа \(n\). Например, для \(n = 4\) число \(17\) является особым, так как может быть представлено как \(4^0 + 4^2 = 1 + 16 = 17\), а вот \(9\) не является.
Теофанис просит вас помочь ему найти \(k\)-е особое число, если они отсортированы в порядке возрастания. Так как данное число может быть слишком большим, выведите его по модулю \(10^9+7\).
Выходные данные
Для каждого набора входных данных выведите одно целое число — \(k\)-е особое число в порядке возрастания по модулю \(10^9+7\).
Примечание
При \(n = 3\), последовательность начинается с \([1,3,4,9...]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 4
2 12
105 564
|
9
12
3595374
|