序列计数
暂无测试数据。
设 $f(n,k)$ 为符合以下条件的所有序列 $a$ 的个数：
- $a$ 的长度为 $n$。
- 对每个 $1\le i\le n$，$a_i\in [1,k]$。
- $a$ 不存在循环节。
其中，序列的循环节定义为：存在一个 $1\le m<n$，使得区间 $[1,m]$ 可以将自身复制若干次后得到原序列。
例如，abcabcabc 有循环节 abc，aaa 有循环节 a，而 YunQian 没有循环节。
云浅并不想让你求出 $f(n,k)$ 的值，不过，她希望你求出
$$\displaystyle \sum_{x=1}^{n}\sum_{d|x}f(d,k)\quad\bmod1000000007 $$
的值。
对于长度为 $1$ 的序列，我们认为它也没有循环节。
输入格式
本题有多组数据。
第一行一个正整数 $T$ 表示数据组数。
接下来 $T$ 行，每行两个正整数 $k,n$。
输出格式
对于每组数据，一行一个正整数表示符合条件的序列个数。
数据范围
| 数据点编号 | 数据范围 |
|---|---|
| $1\sim 4$ | $T=1,n,k\le 5$ |
| $5\sim 8$ | $T=1,n,k\le 100$ |
| $9\sim 14$ | $T=10^5,n,k\le 2\times 10^4$ |
| $15\sim 20$ | 无特殊限制 |
对于 $100\%$ 的数据，$1\leq T\le10^5,1\leq n,k\le 10^{18}$。
3
1 3
2 2
2 3
3
6
14