CF2072G.I've Been Flipping Numbers for 300 Years and Calculated the Sum

经过三百年的史莱姆养殖，Akito 终于获得了魔法数字 $n$。当他找到商人准备兑换黄金时，商人却给了他一个任务。

商人表示，完成这个任务需要用到技能 $\text{rev}(n, p)$，而 Akito 恰好最近学会了这个技能。$\text{rev}(n, p)$ 表示以下操作流程：

1. 将数字 $n$ 以 $p$ 进制表示，记作 $n = \overline{n_{\ell - 1} \ldots n_1 n_0}$，其中 $\ell$ 是 $n$ 的 $p$ 进制表示的位数长度。
2. 反转这个 $p$ 进制表示，得到 $m = \overline{n_0 n_1 \ldots n_{\ell - 1}}$。
3. 将 $m$ 转换回十进制并作为结果返回。

商人的任务是计算总和 $x = \sum\limits_{p = 2}^{k} \text{rev}(n, p)$。由于这个数字可能非常大，只需要输出 $x$ 对 $10^9 + 7$ 取模后的余数。商人还提到，上一个旅行者计算这个和已经用了三百年仍未完成。但你一定会帮助 Akito 更快完成，对吗？

第一行包含一个数 $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$ 取模后的结果。

在第三个测试用例中，$n = 1$。数字 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 = 1 + 4 + 1 = 6$。

在第七个测试用例中，$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$
  因此，$x = 9 + 1 = 10$。

翻译由 DeepSeek R1 完成