Score : 500 points
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.
Input is given from Standard Input in the following format:
N K
Print the sum of \gcd(A_1, ..., A_N) over all K^N sequences, modulo (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
Thus, the answer is 9.
3 200
10813692
100000 100000
742202979
Be sure to print the sum modulo (10^9+7).