[ABC162E] Sum of gcd of Tuples (Hard)
题意翻译
给定$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$$
题目描述
[problemUrl]: https://atcoder.jp/contests/abc162/tasks/abc162_e
$ 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) $ で割ったあまりを出力せよ。
输入输出样例
输入样例 #1
3 2输出样例 #1
9输入样例 #2
3 200输出样例 #2
10813692输入样例 #3
100000 100000输出样例 #3
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 $ で割った余りを出力してください。