### 问题描述 小桥是一个热爱数字的小孩，他总是会发现数字之间的神奇规律，而他的数学老师小蓝，也总是会给他一些有趣的问题。 这一次，小蓝向小桥提出了一个关于神奇数字的问题。神奇数字指的是一种特殊的数字，它可以被表示为 $n$ 的不同非负次幂之和。例如，当 $n=4$ 时，数字 $17$ 是神奇数字，因为它可以被表示为 $4^0+4^2=1+16=17$，但数字 $9$ 不是神奇数字。 小桥想知道，按照从小到大的顺序，第 $k$ 个神奇数字是多少。但由于这个数字可能非常大，所以你需要输出它对 $10^9+7$ 取模后的值。 ### 输入格式 第一行包含一个整数 $t$，表示测试用例的数量。 接下来 $t$ 行，每行包含两个整数 $n$ 和 $k$，表示要求第 $k$ 个神奇数字，其中 $n$ 是基数。 ### 输出格式 对于每个测试用例，输出一行一个整数，表示按照从小到大的顺序，第 $k$ 个神奇数字对 $10^9+7$ 取模后的值。 ### 样例输入 ```txt 3 3 4 2 12 105 564 ``` ### 样例输出 ```txt 9 12 3595374 ``` ### 评测数据规模 对于 $100$% 的评测数据，$1\leq t \leq 10^4, 2 \leq n \leq 10^9, 1 \leq k \leq 10^9$。