A6464. Welcome24ever 与特殊数
编程题
普及-
知识点
题目描述
Welcome24ever 是个聪明的男孩，他非常喜欢正整数序列，于是老师给了 TA 一道关于**只包含特殊数**的序列的题。
定义：若一个正整数能表示为 $n$ 的**不同非负整数次幂之和**，则称其为**特殊数**。
例如，当 $n=4$ 时，$17$ 是特殊数（$17=4^0+4^2$），而 $9$ 不是。
现在给定 $n$ 和 $k$，请你找出**按升序排列**的第 $k$ 个特殊数。由于该数可能很大，请输出它对 $10^9+7$ 取模的结果。
定义：若一个正整数能表示为 $n$ 的**不同非负整数次幂之和**，则称其为**特殊数**。
例如，当 $n=4$ 时，$17$ 是特殊数（$17=4^0+4^2$），而 $9$ 不是。
现在给定 $n$ 和 $k$，请你找出**按升序排列**的第 $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$）。
- 接下来每个测试用例一行，包含两个整数 $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,\ldots]$。
对于 $n=3$，序列为 $[1,3,4,9,\ldots]$。