Grand Prix of Array Count

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, an array $\[6,2,2,2,4]$ is funny.

You are given two positive integers $n$ and $k$. Find the amount of funny arrays of length $n$ consisting only of integers between $1$ and $k$. As this number may be very large, output it modulo $10^9+7$.

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

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

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