CF1594B Special Numbers

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$ 取模的结果。

对于 $n=3$，序列为 $[1,3,4,9,\ldots]$。 由 ChatGPT 4.1 翻译