题目描述

题目大意

考虑长度为$N$的由整数1到$K$(含)构成的序列${A_1,…,A_N}$。

总共有$K^N$个这样的序列。找出所有序列中$gcd(A_1,… A_N)$的和。

由于这个和可能非常大，所以对$(10^9+7)$取模后输出。

这里$gcd(A_1,…, A_N)$表示$A_1,…, A_N$的最大公约数。

输入

第一行输入两个整数$N,K$

输出

输出所有$K^N$个序列中$gcd(A_1,…, A_N)$的和，对$(10^9+7)$取模后的结果.

3 2

9

样例解释

gcd(1,1, 1)+ gcd(1, 1,2)+ gcd(1,2, 1)+ gcd(1,2,2)+ gcd(2, 1,1)+ gcd(2, 1,2)+ gcd(2,2, 1)+gcd(2,2,2)=1+1+1+1+1+1+1+2=9因此，答案为9。

3 200

10813692

100000 100000

742202979

提示

• $2\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ K\ \leq\ 10^5$
• 输入都是整数