P15745 [JAG 2024 Summer Camp #3] Commutativity

You are given a function $F: \{1, 2, \ldots, N\} \rightarrow \{1, 2, \ldots, 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, \ldots, N\} \rightarrow \{1, 2, \ldots, N\}$ such that $F$ and $G$ commute under composition: that is, $F(G(x)) = G(F(x))$ holds for any $x \in \{1, 2, \ldots, N\}$. As this number could be large, print the answer modulo $998,244,353$.

The input consists of a single test case of the following format. $$\begin{aligned} & N \\ & F_{1} \ F_{2} \ \ldots \ F_{N} \end{aligned}$$ 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}, \ldots, 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$.

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