sumgcd

Two numbers, $N$ and $M$, are given. An $M$-tuple is defined as a set of $M$ positive integers, not necessarily distinct, where each number is $\leq N$. For example, for $N = 4$ and $M = 4$, two valid $4$-tuples can be $(2,1,2,3)$, $(4,1,1,3)$, but not $(5,100,4,-10)$ or $(-1,1,1,1)$.

Task

Calculate the sum of greatest common divisors (GCDs) for all $M$-tuples, specifically $\sum_{V} \text{gcd}(V)$, where $V$ is an $M$-tuple, and $\text{gcd}(V)$ is the GCD of the values in the tuple. Since the answer can be very large, it will be displayed modulo $10^9+7$.

Input data

On the first line, two integers are found, $N$ and $M$.

Output data

On the first line, a single integer, the requested result, will be found.

Constraints and clarifications

• $1 \leq N \leq 2 \cdot 10^5$
• $2 \leq M \leq 10^{18}$

Example 1

stdin

3 3

stdout

30

Explanation

Some $3$-tuples, along with their GCD, are:
$(1, 1, 1) \rightarrow 1$
$(1, 1, 2) \rightarrow 1$
$(1, 1, 3) \rightarrow 1$
$(1, 2, 1) \rightarrow 1$
$(1, 2, 2) \rightarrow 1$
$(2, 2, 1) \rightarrow 1$
$(2, 2, 2) \rightarrow 2$
$(2, 2, 3) \rightarrow 1$
$(3, 3, 2) \rightarrow 1$
$(3, 3, 3) \rightarrow 3$

Example 2

stdin

10 2

stdout

189

Example 3

stdin

13756 1005346

stdout

339396382