### 问题描述 作为魂穿皮皮鸡的你，经过一段时间的发展，现在要带领帕鲁们打倒可恶的赛博奴隶主了！ 要打倒一个 boss，首先就要知道 boss 的血量。我们的赛博奴隶主作为最大的 boss，自然也有他的血量。但是他十分狡猾，把自己的血量藏了起来。不过无论如何，他必须提供一种方式让帕鲁们知道他的血量。赛博奴隶主所提供的方式如下： 赛博奴隶主把头顶上的血量变成了一个数字 $n$，他的实际血量为 $n$ 的所有约数的 $k$ 次方之和，然后再对 $10^9+7$ 取余。 举个例子，如果 $n=9$，$k=3$，那么赛博奴隶主的实际血量为 $(1^3 + 3^3 + 9^3) \bmod (10^9+7) = 757$。 你现在需要做的就是求出赛博奴隶主的血量，然后带领帕鲁们一起打败他！让我们解放帕鲁吧！  ### 输入格式 第一行输入 $1$ 个正整数 $t$，表示测试案例组数。（$2\leq t\leq 10^2$）。 接下来 $t$ 行，每行输入 $2$ 个正整数 $n,k$，其中 $n $ 表示赛博奴隶主的血条，$k$ 表示 $k$ 次方的血量转化比。（$1\leq n,k \leq 10^{18}$）。 ### 输出格式 输出 $t$ 行，每行包含一个正整数，表示对应赛博奴隶主真实的血量，注意！这个结果是对 $10^9+7$ 取模后的结果。 ### 样例输入 ```text 3 3 1 4 2 4 1 ``` ### 样例输出 ```text 4 21 7 ``` ### 说明 对于样例： $4=1+3$。 $21=1+4+16$。 $7=1+2+4$。