問題一覧 > 通常問題

No.1973 Divisor Sequence

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

問題文

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

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

  • 要素数は $N$ である。
  • 要素はすべて $1$ 以上の整数である。
  • $1 \leq i \leq N-1$ を満たす任意の $i$ において、$A_i \times A_{i+1}$ は $M$ の約数である。

(数列 $A$ の $i$ 個目の要素を $A_i$ と表記しています。)

制約

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

入力

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

$N\ \ M$

出力

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

サンプル

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

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

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

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

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

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