sumgcd

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

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

Task

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

Input data

On the first line, two integers are found, NN and MM.

Output data

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

Constraints and clarifications

  • 1N21051 \leq N \leq 2 \cdot 10^5
  • 2M10182 \leq M \leq 10^{18}
# Points Constraints
1 13 1N,M101 \leq N,M \leq 10
2 23 1N,M1001 \leq N,M \leq 100
3 24 1N1041 \leq N \leq 10^4, 2M10122 \leq M \leq 10^{12}
4 40 No additional constraints

Example 1

stdin

3 3

stdout

30

Explanation

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

Example 2

stdin

10 2

stdout

189

Example 3

stdin

13756 1005346

stdout

339396382

Log in or sign up to be able to send submissions!