Description

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$.

Input Format

The first line contains an integer $n$.

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

Output Format

Output the answer.

3
2 1 3

1

Hint

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