小A和小C在玩一个游戏，每次小A从$1$~$n$中任意选择一个数$i$，然后小C从$1$~$i$中任意选择一个数$x$，这将会产生$gcd(i,x)$的价值。众所周知，小C是一个复读机，他会重复$k$次这样的操作，游戏的总价值为每次小C产生价值的最小公倍数。

现在小A想要知道所有情况下游戏总价值的和是多少，由于一些显而易见的原因，你只需要求出在模${10}^9+7$意义下的和即可。

输入格式

一行两个正整数$n,k$。

输出格式

一行一个整数，表示游戏的价值和。

样例一

input

3 1

output

9

explanation

对于Sample Input 1 价值为 $gcd(1,1)+gcd(2,1)+gcd(2,2)+gcd(3,1)+gcd(3,2)+gcd(3,3)=9$

样例二

input

5 2

output

130

样例三

input

1000000 1000

output

763267594

限制与约定

$1\le n\le {10}^9,1\le k\le {10}^9,1\le n\ast k\le {10}^9$

本题使用子任务评测（空则表示无特殊性质）

时间限制：$\mathtt{\text{2s}}$

空间限制：$\mathtt{\text{512MB}}$

下载

样例数据下载