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...]$$$