When \(M\) is represented as \(M=p_1^{q_1} p_2^{q_2} p_3^{q_3}\ldots \) with primes \(p_1,p_2,p_3,\ldots\), the answer for the original problem can be found by solving for each \((p_1,q_1),(p_2,q_2),(p_3,q_3),\ldots\) the following problem:

Let \(p\) be a prime and \(q\) be a positive integer. How many sequences \(a\) of length \(K\) are there that satisfy the following conditions? \(\cdots (*)\)

• For each \(i(1\leq i \leq K)\), \(0\leq a_i \leq p^q - 1\);
• \(\displaystyle \prod_{i=1}^{K}a_i \equiv N \pmod {p^q}\).

and find their product.

we consider \((*)\). Let \( F(p,q,K,N)\) be the answer for \((*)\).

When \(N_1\) and \(N_2\) has the same \(p\)-adic order, then \(F(p,q,K,N_1)=F(p,q,K,N_2)\) holds. (This can be proved by induction.)
Therefore, for fixed \(p\), \(q\), and \(K\), there are about \(O(\log_{ p}N)\) distinct values of \(F(p,q,K,N)\). Moreover, \(F(p,q,k,n)\) can be found as a sum of a linear combination of \(F(p,q,k-1,n')\), so \((*)\) can be solved by means of fast matrix exponentiation.

Hence, the problem has been solved.

Supplement

Depending on implementation, divisions by \((p-1)\) or \(p\) may occur. Note that this may cause division-by-zero if they are multiples of \(998244353\).