問題一覧 > 通常問題

No.1973 Divisor Sequence

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 111
作問者 : magsta / テスター : nok0
お気に入りにしたユーザー ProblemId : 5501 / 自分の提出
問題文最終更新日: 2022-06-08 20:14:05
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 347 (順位表) の他の問題:

Problem Statement

You are given positive integers $N, M$.

How many sequences $A$ satisfy all of the following conditions? Find the count modulo $10^9+7$.

  • The number of elements is $N$.
  • All elements are integers greater than or equal to $1$.
  • For every $i$ satisfying $1 \leq i \leq N-1$, $A_i \times A_{i+1}$ is a divisor of $M$.

(The $i$-th element of the sequence $A$ is denoted by $A_i$.)

Constraints

  • $\displaystyle 2 \leq N \leq 5×10^5$
  • $\displaystyle 1 \leq M \leq 10^{12}$
  • All inputs are integers

Input

The input is given from standard input in the following format. 

$N\ \ M$

Output

Output the computed value, followed by a newline.

Sample

Sample 1
Input
2 4
Output
6

$(1,1),(1,2),(1,4),(2,1),(2,2),(4,1)$ are the sequences that satisfy the conditions.

Sample 2
Input
27 1
Output
1

The conditions are satisfied only when all elements are $1$.

Sample 3
Input
487213 291398322010
Output
227156497

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