# sumgcd

Time limit: 0.4s Memory limit: 64MB Input: Output:

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)$.

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}$
# Points Constraints
1 13 $1 \leq N,M \leq 10$
2 23 $1 \leq N,M \leq 100$
3 24 $1 \leq N \leq 10^4$, $2 \leq M \leq 10^{12}$
4 40 No additional constraints

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

stdin

10 2

stdout

189

stdin

13756 1005346

stdout

339396382