配点 : $500$ 点

問題文

$1$ 以上 $K$ 以下の整数からなる長さ $N$ の数列 $\{A_1,...,A_N\}$ を考えます。

そのようなものは $K^N$ 個ありますが、その全てについての $\gcd(A_1,...,A_N)$ の和を求めてください。

ただし、答えは非常に大きくなる可能性があるため、和を $(10^9+7)$ で割ったあまりを出力してください。

なお、$\gcd(A_1,...,A_N)$ は $A_1,...,A_N$ の最大公約数を表します。

制約

• $2 \leq N \leq 10^5$
• $1 \leq K \leq 10^5$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

$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

和を $10^9+7$ で割った余りを出力してください。