No.644 G L C C D M
タグ : / 解いたユーザー数 52
作問者 :
Pulmn
/ テスター :
square1001
問題文
以下の条件を満たす $(1,2,\dots,N)$ の順列 $A$ の通り数を求めてください。ただし、この値は非常に大きくなる場合があるので $1{,}000{,}000{,}007$ で割った時の余りを出力してください。
条件：$A$ に対して次の操作を $N-1$ 回行ったとき、$A_1=M$ が成り立つ。
操作後の数列を $B$ とします。
操作：数列 $B$ の長さは $( A の長さ) - 1$ であり、$1\le i\le (Aの長さ)-1$を満たす全ての $i$ において、
$$ \begin{aligned}\ B_i=\begin{cases}gcd(A_i,A_{i+1})&(iが奇数) \\ lcm(A_i,A_{i+1})&(iが偶数) \end{cases}\end{aligned} $$
が成り立つ。
なお、$gcd(x,y)$ は $x$ と $y$ の最大公約数、$lcm(x,y)$ は $x$ と $y$ の最小公倍数を表す。
入力
$N$ $M$
$2\le N\le 10^5,1\le M\le 10^9$
出力
条件を満たす順列 $A$ の通り数を $1{,}000{,}000{,}007$ で割った時の余りを出力してください。最後に改行してください。
サンプル
サンプル1
入力
3 1
出力
6
$(1,2,3)$ の順列すべてが条件を満たします。例えば$A=\{3,1,2\}$の場合、
$1$回目の操作後：$A=\{gcd(3,1),lcm(1,2)\}=\{1,2\}$
$2$回目の操作後：$A=\{gcd(1,2)\}=\{1\}$
サンプル2
入力
2 1
出力
2
サンプル3
入力
3 100
出力
0
$(1,2,3)$ の順列 $A$ に対し $2$ 回操作を行ったとき、常に $A_1=1$ が成り立つので、条件を満たす順列は$0$通りです。
サンプル4
入力
100 30
出力
945719957
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。