E - Sum of gcd of Tuples (Hard) /

Time Limit: 2 sec / Memory Limit: 1024 MB

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


入力例 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 で割った余りを出力してください。

Score : 500 points

Problem Statement

Consider sequences \{A_1,...,A_N\} of length N consisting of integers between 1 and K (inclusive).

There are K^N such sequences. Find the sum of \gcd(A_1, ..., A_N) over all of them.

Since this sum can be enormous, print the value modulo (10^9+7).

Here \gcd(A_1, ..., A_N) denotes the greatest common divisor of A_1, ..., A_N.

Constraints

  • 2 \leq N \leq 10^5
  • 1 \leq K \leq 10^5
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (10^9+7).


Sample Input 1

3 2

Sample Output 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

Thus, the answer is 9.


Sample Input 2

3 200

Sample Output 2

10813692

Sample Input 3

100000 100000

Sample Output 3

742202979

Be sure to print the sum modulo (10^9+7).