题目描述

Consider sequences $\{A_1,...,A_N\}$ of length $N$ consisting of integers between $1$ and $K$ (inclusive).

There are $K^N$ such sequences. Find the sum of $\gcd(A_1, ..., A_N)$ over all of them.

Since this sum can be enormous, print the value mod $(10^9+7)$.

Here $\gcd(A_1, ..., A_N)$ denotes the greatest common divisor of $A_1, ..., A_N$.

考虑长度为 $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$ 的最大公因子。

输入格式

输入内容按以下格式标准输入：

$N$ $K$

输出格式

打印所有 $K^N$ 序列上 $\gcd(A_1, ..., A_N)$ 的和，模为 $(10^9+7)$ 。

样例 #1

样例输入 #1

3 2

样例输出 #1

9

样例 #2

样例输入 #2

3 200

样例输出 #2

10813692

样例 #3

样例输入 #3

100000 100000

样例输出 #3

742202979

说明

数据规模与约定

• $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)$ 的模数和。