小A和小C在玩一个游戏，每次小A从$1$~$n$中任意选择一个数$i$，然后小C从$1$~$i$中任意选择一个数$x$，这将会产生$\gcd(i,x)$的价值。众所周知，小C是一个复读机，他会重复$k$次这样的操作，游戏的总价值为每次小C产生价值的最小公倍数。
现在小A想要知道所有情况下游戏总价值的和是多少，由于一些显而易见的原因，你只需要求出在模$10^9+7$意义下的和即可。
输入格式
一行两个正整数$n,k$。
输出格式
一行一个整数，表示游戏的价值和。
样例一
input
3 1output
9explanation
对于Sample Input 1 价值为 $\gcd(1,1)+\gcd(2,1)+\gcd(2,2)+\gcd(3,1)+\gcd(3,2)+\gcd(3,3)=9$
样例二
input
5 2output
130样例三
input
1000000 1000output
763267594限制与约定
$1 \le n \le 10^9, 1 \le k \le 10^9, 1 \le n*k \le 10^9$
本题使用子任务评测（空则表示无特殊性质）
| 子任务 | 分值 | $n$ | $k$ |
|---|---|---|---|
| 1 | 5 | $\leq 10^6$ | $= 1$ |
| 2 | 5 | $= 1$ | |
| 3 | 7 | $\leq 10^6$ | $= 2$ |
| 4 | 8 | $= 2$ | |
| 5 | 35 | $\leq 10^7$ | |
| 6 | 40 |
时间限制：$\texttt{2s}$
空间限制：$\texttt{512MB}$
鄂公网安备 42010202000505 号