問題文

$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)$ で割ったあまりを出力せよ。

入力例 1

3 2

出力例 1

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$ です。

入力例 2

3 200

出力例 2

10813692

入力例 3

100000 100000

出力例 3

742202979

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