经过三百年的史莱姆养殖,秋人终于获得了神奇的数字$$$n$$$。到达商人后,他想用号码换取黄金,但商人给了英雄一个任务。
商人说,这个任务需要技能$$$\text{rev}(n, p)$$$,这是秋人最近学到的,巧合的是。 $$$\text{rev}(n, p)$$$ 表示以下过程:
- 将数字$$$n$$$写入基数$$$p$$$,令该表示形式为$$$n = \overline{n_{\ell - 1} \ldots n_1 n_0}$$$,其中$$$\ell$$$是数字$$$n$$$的基数$$$p$$$表示形式的长度。
- 反转基本 $$$p$$$ 表示,令其为 $$$m = \overline{n_0 n_1 \ldots n_{\ell - 1}}$$$。
- 将数字 $$$m$$$ 转换回十进制并将其作为结果返回。
商家的任务是计算总和 $$$x = \sum\limits_{p = 2}^{k} \text{rev}(n, p)$$$。由于这个数字可能相当大,因此只需要 $$$x$$$ 除以 $$$10^9 + 7$$$ 后的余数。商人还提到,之前的旅人已经计算了这个数字三百年了,还没有算完。但你会帮助秋人更快地完成它,对吗?
输入
第一行包含数字 $$$t$$$ ($$$1 \le t \le 5000$$$) — 测试用例的数量。
在每个测试用例的唯一行中,给出了两个数字 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 3 \cdot 10^5, 2 \le k \le 10^{18}$$$) — 神奇数字和求和的上限。
请注意 总和 $$$n$$$ 所有测试用例都不受限制.
输出
对于每个测试用例,您需要输出一个数字 - $$$x = \sum\limits_{p = 2}^{k} \text{rev}(n, p)$$$ 除以 $$$10^9 + 7$$$ 的余数。
示例
输入复制
123 242 521 104 416 269 699 319 849982 44353100000 100000000717 30777 1000000000000000000
输出复制
3 7594 9 6 1 33471 10 2006 120792461 584502117 775 46058362
注意
在第三个测试用例中,$$$n = 1$$$。任何数字系统中的数字一均由单个数字表示,这意味着对于任何 $$$p \ge 2$$$,$$$\text{rev}(1, p) = 1$$$。因此,$$$x = \sum\limits_{p = 2}^{k} 1 = \sum\limits_{p = 2}^{10} 1 = 10 - 2 + 1 = 9$$$。
在第四个测试用例中,$$$x = \text{rev}(4, 2) + \text{rev}(4, 3) + \text{rev}(4, 4)$$$。让我们计算每一项:
- $$$4 = 100_2 \rightarrow \text{rev}(4, 2) = 001_2 = 1$$$
- $$$4 = 11_3 \rightarrow \text{rev}(4, 3) = 11_3 = 4$$$
- $$$4 = 10_4 \rightarrow \text{rev}(4, 4) = 01_4 = 1$$$
在第七个测试用例中,$$$x = \text{rev}(9, 2) + \text{rev}(9, 3)$$$。让我们计算每一项:
- $$$9 = 1001_2 \rightarrow \text{rev}(9, 2) = 1001_2 = 9$$$
- $$$9 = 100_3 \rightarrow \text{rev}(9, 3) = 001_3 = 1$$$