题目描述

若将 $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

5

数据范围

对于 $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}$。