E - 元组$\gcd$之和 (困难)

分数：500分

问题描述

考虑长度为$N$的由整数$1$到$K$（含）构成的序列$\{A_1,...,A_N\}$。

总共有$K^N$个这样的序列。找出所有序列中$\gcd(A_1, ..., A_N)$的和。

由于这个和可能非常大，所以对$(10^9+7)$取模后输出。

这里$\gcd(A_1, ..., A_N)$表示$A_1, ..., A_N$的最大公约数。

约束条件

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

输入

输入从标准输入中读取，具体格式如下：

$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)$取模后输出。