問題一覧 > 通常問題

No.644 G L C C D M

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 : PulmnPulmn / テスター : square1001square1001
4 ProblemId : 1665 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-25 02:19:48

問題文

以下の条件を満たす $(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もしくは右上の雲マークをクリックしてアカウントを作成してください。