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

考虑由 $1$ 到 $K$ 之间的整数构成的长度为 $N$ 的数列 $\{A_1, \ldots, A_N\}$。 这样的数列共有 $K^N$ 个。请你计算所有这些数列的 $\gcd(A_1, \ldots, A_N)$ 的和。 由于答案可能非常大，请输出该和除以 $10^9+7$ 的余数。 其中，$\gcd(A_1, \ldots, A_N)$ 表示 $A_1, \ldots, A_N$ 的最大公约数。

输入以以下格式从标准输入读入。 > $N$ $K$

请输出所有 $K^N$ 个数列的 $\gcd(A_1, \ldots, A_N)$ 的和除以 $10^9+7$ 的余数。

## 限制条件 - $2 \leq N \leq 10^5$ - $1 \leq K \leq 10^5$ - 输入均为整数 ## 样例解释 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$。 ## 样例解释 3 请输出该和除以 $10^9+7$ 的余数。 由 ChatGPT 4.1 翻译