No.644 G L C C D M

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 37
作問者 : PulmnPulmn / テスター : square1001square1001
1 ProblemId : 1665 / 出題時の順位表
問題文最終更新日: 2018-11-09 22:59:18

問題文

以下の条件を満たす $(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{eqnarray}\ B_i=\begin{cases}gcd(A_i,A_{i+1})&(iが奇数) \\ lcm(A_i,A_{i+1})&(iが偶数) \end{cases}\end{eqnarray}$  が成り立つ。
   なお、$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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。