288 : 巨大階乗

任意の素数$p$に対し$N(p,q) = \sum_{n=0}^q T_n \times p^n$とする。 $T_n$は以下の乱数生成器で生成する：

$S_0 = 290797$ $S_{n+1} = S_n^2 \mod 50515093$ $T_n = S_n \mod p$

$\textrm{Nfac}(p,q)$を$N(p,q)$の階乗とする。 $\textrm{NF}(p,q)$を$\textrm{Nfac}(p,q)$内の因数 p の個数とする。

$\textrm{NF}(3,10000) \mod 3^{20}=624955285$であることがわかる。

$\textrm{NF}(61,10^7) \mod 61^{10}$を求めよ。