問題一覧 > 通常問題

No.1973 Divisor Sequence

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 107
作問者 : magsta / テスター : nok0
10 ProblemId : 5501 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-08 20:14:05

問題文

正の整数 N,MN, M が与えられます。

以下の条件全てを満たす数列 AA は何通りあるでしょうか。総数を 109+710^9+7 で割った余りを求めてください。

  • 要素数は NN である。
  • 要素はすべて 11 以上の整数である。
  • 1≤i≤N−11 \leq i \leq N-1 を満たす任意の ii において、Ai×Ai+1A_i \times A_{i+1} は MM の約数である。

(数列 AA の ii 個目の要素を AiA_i と表記しています。)

制約

  • 2≤N≤5×105\displaystyle 2 \leq N \leq 5×10^5
  • 1≤M≤1012\displaystyle 1 \leq M \leq 10^{12}
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられる。 

N  MN\ \ M

出力

求めた値を出力し、最後に改行せよ。

サンプル

サンプル1
入力
2 4
出力
6

(1,1),(1,2),(1,4),(2,1),(2,2),(4,1)(1,1),(1,2),(1,4),(2,1),(2,2),(4,1) が条件を満たす数列です。

サンプル2
入力
27 1
出力
1

全要素が 11 のときのみ条件を満たします。

サンプル3
入力
487213 291398322010
出力
227156497

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。