UOJ Logo Universal Online Judge

UOJ

#448. 【集训队作业2018】人类的本质

统计

小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*k \le 10^9$

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

子任务分值$n$$k$
15$\leq 10^6$$= 1$
25 $= 1$
37$\leq 10^6$$= 2$
48 $= 2$
535$\leq 10^7$ 
640  

时间限制:$\texttt{2s}$

空间限制:$\texttt{512MB}$

下载

样例数据下载