/ 
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).