该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个正整数 $n$。对于一个进制 $p$，定义 $\operatorname{rev}(n,p)$ 为下面的操作结果：

1. 将 $n$ 写成 $p$ 进制表示，记为

其中 $\ell$ 是表示长度。

2. 将这个 $p$ 进制表示反转，得到

3. 把 $m$ 按 $p$ 进制转回十进制，返回这个值。

现在给定 $n$ 和 $k$，请计算

由于答案可能很大，只需要输出 $x$ 对 $10^9+7$ 取模后的结果。

输入格式

第一行包含一个整数 $t$，表示测试用例个数。

接下来 $t$ 行，每行包含两个整数 $n,k$。

输出格式

对于每个测试用例，输出一行一个整数，表示

的值。

数据范围

• $1\le t\le 5000$
• $1\le n\le 3\cdot 10^5$
• $2\le k\le 10^{18}$
• 多个测试用例中 $n$ 的总和没有额外限制。

样例

输入

12
3 2
42 52
1 10
4 4
16 2
69 69
9 3
19 84
9982 44353
100000 1000000007
17 30
777 1000000000000000000

输出

3
7594
9
6
1
33471
10
2006
120792461
584502117
775
46058362

样例解释

第三个测试用例中，$n=1$。数字 $1$ 在任何进制下都只有一位，因此对所有 $p\ge 2$ 都有 $\operatorname{rev}(1,p)=1$。所以答案为 $10-2+1=9$。

第四个测试用例中：

• $4=100_2$，反转后为 $001_2=1$；
• $4=11_3$，反转后仍为 $11_3=4$；
• $4=10_4$，反转后为 $01_4=1$。

因此答案为 $1+4+1=6$。