P4709 Information Transmission

Given a permutation $$ f = \begin{pmatrix} 1 & 2 & ... & n \\\ a_1 & a_2 & ... & a_n \end{pmatrix} $$ find how many permutations $g$ satisfy $$ g ^ n = f $$ Output the answer modulo $998244353$.

The first line contains an integer $n$. The second line contains $n$ integers $a_1, a_2, ..., a_n$.

Output the answer.

Sample explanation: There is only one permutation with $a_1 = 2, a_2 = 1, a_3 = 3$ that satisfies $$ {\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix}} ^ 3 = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{pmatrix} $$ Constraints: For $20\%$ of the testdata, $n \le 10$. For $60\%$ of the testdata, $n \le 1000$. For $100\%$ of the testdata, $n \le {10} ^ 5$. Translated by ChatGPT 5