题目描述

$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$ の最大公約数を表します。

输入格式

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

$N$ $K$

输出格式

$K^N$ 個の数列全てについての $\gcd(A_1,...,A_N)$ の和を $(10^9+7)$ で割ったあまりを出力せよ。

题目大意

给定$n,k$，求

$$\sum^k_{a_1=1}\sum^k_{a_2=1}\sum^k_{a_3=1}\dots\sum^k_{a_n=1}gcd(a_1,a_2,a_3,\dots,a_n)\ mod\ 1000000007 $$

3 2

9

3 200

10813692

100000 100000

742202979

提示

制約

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

Sample Explanation 1

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

Sample Explanation 3

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