Grand Prix of Array Count

길이가 $n$인 배열 $a$에서, $1 \le i, j \le n$을 만족하는 모든 인덱스 쌍 $(i, j)$에 대해 다음 조건이 성립하면 이 배열을 funny 배열이라고 한다. $i+j$가 짝수이면 $a_{(i+j)/2} = \mathrm{gcd}(a_i, a_j)$이다. 예를 들어 배열 $[6,2,2,2,4]$는 funny 배열이다.

두 양의 정수 $n$과 $k$가 주어진다. 원소가 모두 $1$ 이상 $k$ 이하인 정수로 이루어진 길이 $n$의 funny 배열의 개수를 구하라. 이 값은 매우 클 수 있으므로 $10^9+7$로 나눈 나머지를 출력하라.

첫 줄에 두 정수 $n$과 $k$가 주어진다 ($5 \le n \le 10^{12}$, $2 \le k \le 10^{12}$).

문제의 답을 $10^9+7$로 나눈 나머지 하나를 출력하라.

첫 번째 테스트에서 funny 배열은 $4$개다. 그 배열은 $[1,1,1,1,1]$, $[1,1,1,1,2]$, $[2,1,1,1,1]$, $[2,2,2,2,2]$이다.