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

  • 1≤N≤2â‹…1051 \leq N \leq 2 \cdot 10^5
  • 2≤M≤10182 \leq M \leq 10^{18}
# Points Constraints
1 13 1≤N,M≤101 \leq N,M \leq 10
2 23 1≤N,M≤1001 \leq N,M \leq 100
3 24 1≤N≤1041 \leq N \leq 10^4, 2≤M≤10122 \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!