C. starback の简单数学题

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

若将 $n$ 分解为 $\prod_{i=1,p_i\in Prime}^{k}p_i^{c_i}$ ，设：

$$ds(n)=\prod_{i=1}^kp_i\\ f_0(n)=\sum_{u\cdot v=(ds(n))}1\\ f_r(n)=\sum_{d\mid n} f_{r-1}(d)$$

给定 $r,n$ ，求出 $f_r(ds(n))$ ，答案对 $10^9+7$ 取模。

一行两个整数 $r,n$ 。

一行一个整数，表示答案。

3 2

对于 $10\%$ 的数据，满足 $1\le r,n\le5$ 。

对于 $50\%$ 的数据，满足 $1\le r\le 10^{18}，1\le n\le 10^{12}$ 。

对于另外 $10\%$ 的数据，满足 $n\in P$ ，其中 $P$ 为质数集合。

对于 $100\%$ 的数据，满足 $1\le r,n\le 10^{18}$ 。