题目描述

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

5
4 5 3 2 1

5

8
2 3 1 3 6 7 5 5

64

10
3 1 4 1 5 9 2 6 5 3

64

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

567381138