ABC110 D. Factorization

問題

整数N, Mが与えられる。
a_1 * a_2 * ... * a_N = Mであるような、長さNの数列aの何通りあり得るか10^9+7で割ったあまりで答えよ。
ただし、数列aとbが異なるとは、あるiが存在してa_i != b_iであることをいう。

制約

• 1 <= N <= 10^5
• 1 <= M <= 10^9

解法

(約数を列挙したDPや行列累乗では、TLEしてしまう。約数でダメなら素因数分解して考える。)

それぞれのMやa_iについて、素因数分解したものを考える。
M = p_1^b_1 * p_2^b_2 * ...
a_i = p_1^x_i1 * p_2^x_i2 * ...
このとき、各p_jについて、b_j = Σx_ijになっていれば、条件を満たす。

そのようなx_ijの割り振り方は、重複組合せC(b_j + N-1, b_j)で求められるので、各p_jに対する重複組合せの積が答えになる。

ただし、M=1のときは1*1*1*1*...の1通りなのに注意。