题目描述

考虑长度为 $N$ 的序列 $\\{A_1,...,A_N\\}$，其中的元素取值范围为 $1$ 到 $K$（包含边界）。

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

示例输入1

3 2

示例输出1

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$。

示例输入2

3 200

示例输出2

10813692

示例输入3

100000 100000

示例输出3

742202979

请务必对和取模 $(10^9+7)$ 后输出。