← 返回题目列表

Codeforces · 1594/B

B. 特殊号码

中文机器翻译题面 查看原题

Theofanis 非常喜欢正整数序列,因此他的老师(Yeltsa Kcir)给了他一个关于仅由特殊数字组成的序列的问题。

如果一个正数可以写成 $$$n$$$ 的不同非负幂的和,我们将其称为特殊数。例如,对于 $$$n = 4$$$ 数字 $$$17$$$ 是特殊的,因为它可以写为 $$$4^0 + 4^2 = 1 + 16 = 17$$$,但 $$$9$$$ 则不然。

Theofanis 要求你帮助他找到第 $$$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$$$ 模递增顺序排列。

示例

输入 #1

3
3 4
2 12
105 564

输出 #1

9
12
3595374

注意

对于 $$$n = 3$$$,序列为 $$$[1,3,4,9...]$$$