AT_abc162_e [ABC162E] Sum of gcd of Tuples (Hard)

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

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