Commutativity

Problem Statement

You are given a function $F: \{1, 2, ..., N\} \rightarrow \{1, 2, ..., N\}$. In other words, $F$ is a function that takes an integer $x$ between $1$ and $N$ inclusive and returns an integer $F(x)$ between $1$ and $N$ inclusive. Your task is to count the number of functions $G:\{1, 2, ..., N\} \rightarrow \{1, 2, ..., N\}$ such that $F$ and $G$ commute under composition: that is, $F(G(x))=G(F(x))$ holds for any $x \in \{1, 2, ..., N\}$.

As this number could be large, print the answer modulo $998,244,353$.

Input

The input consists of a single test case of the following format.

$N$
$F_1$ $F_2$ ... $F_N$

The first line consists of an integer $N$ between $1$ and $5,000$, inclusive. The second line consists of $N$ positive integers $F_1, F_2, ..., F_N$. For each $i$ ($1 \leq i \leq N$), $F_i$ represents the value of $F(i)$. It is guaranteed that $1 \leq F_i \leq N$.

Output

Print the number of possible functions $G: \{1, 2, ..., N\} \rightarrow \{1, 2, ..., N\}$ modulo $998,244,353$.

Sample Input 1

5
4 5 3 2 1

Sample Output 1

5

Sample Input 2

8
2 3 1 3 6 7 5 5

Sample Output 2

64

Sample Input 3

10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

64

Sample Input 4

15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Sample Output 4

567381138

---