Grand Prix of Array Count

Time limit1sMemory limit2048 MB

Summary

Count arrays of length n with values from 1 to k where a[(i+j)/2] equals gcd(a[i], a[j]) for every pair with i+j even, modulo 1e9+7.

Level: Hard9 of 10
Topics: Math, Number theory, Combinatorics
Solved: No attempts yet

Problem

An array $a$ of length $n$ is called funny if, for every pair of indices $(i, j)$ where $1 \le i, j \le n$ , the following condition holds: if $i+j$ is an even number, then $a_{(i+j)/2} = \mathrm{gcd}(a_i, a_j)$ . For example, the array $[6,2,2,2,4]$ is funny.

You are given two positive integers $n$ and $k$ . Find the number of funny arrays of length $n$ whose elements are integers between $1$ and $k$ . Since this number can be very large, print it modulo $10^9+7$ .

Input

The only line contains two integers $n$ and $k$ ( $5 \le n \le 10^{12}$ , $2 \le k \le 10^{12}$ ).

Output

Print a single number: the answer to the problem modulo $10^9+7$ .

Hint

In the first sample, there are $4$ funny arrays: $[1,1,1,1,1]$ , $[1,1,1,1,2]$ , $[2,1,1,1,1]$ , $[2,2,2,2,2]$ .

Examples2

Example 1
Input
```
5 2
```
Expected output
```
4
```
Example 2
Input
```
32 5
```
Expected output
```
32
```