Problem Archive

For any prime $p$ the number $N(p, q)$ is defined by $N(p, q) = \sum_{n = 0}^q T_n \cdot p^n$
with $T_n$ generated by the following random number generator:

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

Let $\operatorname{Nfac}(p, q)$ be the factorial of $N(p, q)$.
Let $\operatorname{NF}(p, q)$ be the number of factors $p$ in $\operatorname{Nfac}(p, q)$.

You are given that $\operatorname{NF}(3,10000) \bmod 3^{20} = 624955285$.

Find $\operatorname{NF}(61, 10^7) \bmod 61^{10}$.