说明

输入文件: gcdlcm.in 输出文件: gcdlcm.out 时间限制: 1 Sec 内存限制: 256 MB

题目描述

请计算满足以下条件的 $ (1, 2, \dots, N) $ 的排列 $ A $ 的数量。由于该数值可能极大，需输出其对 $ 1,000,000,007 $ 取余的结果。

条件：对排列 $ A $ 执行下述操作 $ N-1 $ 次后，最终得到的结果等于 $ M $。

操作定义如下：

设操作后得到的数列为 $ B $，则 $ B $ 的长度为“原数列 $ A $ 的长度 $ - 1 $”。对于所有满足 $ 1 \leq i \leq (\text{原数列 } A \text{ 的长度} - 1) $ 的 $ i $，均有：

$$ \begin{aligned} B_i=\begin{cases}  \gcd(A_i, A_{i+1}) & (i \text{ 为奇数时}) \\ \\  \text{lcm}(A_i, A_{i+1}) & (i \text{ 为偶数时}) \end{cases} \end{aligned} $$

其中，$ \gcd(x, y) $ 表示 $ x $ 与 $ y $ 的最大公约数，$ \text{lcm}(x, y) $ 表示 $ x $ 与 $ y $ 的最小公倍数。

输入格式

一行，两个整数 $N$ 和 $M$。

输出格式

一个整数，表示答案。

样例

3 1

6

样例说明 #1

(1, 2, 3) 的所有排列都满足条件。

例如，当排列 $A = \{3, 1, 2\}$ 时：

• 第 1 次操作后：数列变为 $\{gcd(3, 1), lcm(1, 2)\} = \{1, 2\}$；
• 第 2 次操作后：数列变为 $\{gcd(1, 2)\} = \{1\}$。

2 1

2

3 100

0

100 30

945719957

数据范围

• 对于 15% 的数据，$N \leq 100$；
• 对于 30% 的数据，$N \leq 1000$；
• 对于 60% 的数据，$N \leq 10000$；
• 对于 100% 的数据，$2 \leq N \leq 10^5$，$1 \leq M \leq 10^9$。