如果一个长度为 $n$ 的数组 $a$ 满足以下条件，则称其为“有趣的”：对于每一对满足 $1 \le i, j \le n$ 的下标 $(i, j)$，如果 $i + j$ 是偶数，则 $a_{(i+j)/2} = \gcd(a_i, a_j)$。例如，数组 $[6, 2, 2, 2, 4]$ 就是有趣的。

给定两个正整数 $n$ 和 $k$。求长度为 $n$ 且仅由 $1$ 到 $k$ 之间的整数组成的有趣数组的数量。由于该数字可能非常大，请输出其对 $10^9 + 7$ 取模的结果。

输入格式

仅一行，包含两个整数 $n$ 和 $k$ ($5 \le n \le 10^{12}, 2 \le k \le 10^{12}$)。

输出格式

输出一个整数：问题的答案对 $10^9 + 7$ 取模的结果。

样例

输入 1

5 2

输出 1

4

输入 2

32 5

输出 2

32

说明

在第一个样例中，共有 4 个有趣的数组：$[1, 1, 1, 1, 1], [1, 1, 1, 1, 2], [2, 1, 1, 1, 1], [2, 2, 2, 2, 2]$。