数列最大公约数之和(困难)

题目描述

考虑由 $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)$ 的余数。

样例

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$, 所以答案为 $9$。

3 200

10813692

100000 100000

742202979

请输出将和除以 $10^9+7$ 得到的余数。

数据范围

• $2 \leq N \leq 10^5$
• $1 \leq K \leq 10^5$
• 输入均为整数