题目描述

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 翻译

样例

3
3 4
2 12
105 564

9
12
3595374