No.004 D

$\vert N \vert$ を素因数分解し, その結果を $\prod_i p_i^{q_i}$ とする.

整数の積の順序を区別するので, $\vert N \vert$ を $M$ 個の積で表す組み合わせの数は, 各素因数を $M$ 個の箱に入れていく組み合わせの数に等しい.

$q_i$ 個の $p_i$ を $M$ 個の箱に入れる組み合わせの数は, $q_i$ 個の玉と $M-1$ 個の仕切りを並べる組み合わせの数に等しいので, ${}_{q_i+M-1}C_{q_i}$ である. よって $\vert N \vert$ を $M$ 個の積で表す組み合わせの数は,

$$S_1 = \prod_i {}_{q_i+M-1}C_{q_i}$$

となる.

次に, 各項のプラスマイナスの組み合わせを考える.

$N \gt 0$ ならば偶数個のマイナスがあることになる. よって, 組み合わせの数は

$$S_2 = \sum_{i \in even} {}_MC_i$$

となる. $N \lt 0$ の場合は奇数個のマイナスがあることになり, 同様に計算できる.

あとはこれを掛けて $S_1S_2$ が答えとなる.

${}_nC_r$ は階乗と逆元をあらかじめ計算しておけば $O(1)$ で計算できる.

なお, $\vert N \vert \leq 10^9$ なので $p_i$ の個数は最大でも $9$, $q_i$ は最大でも $30$ である.