409137: GYM103446 B Strange Permutations

Given a permutation $$$P$$$ of $$$\{1,2,\cdots, n\}$$$, determine the number of $$$\{1,2,\cdots, n\}$$$ permutations $$$Q$$$ satisfying that $$$\forall i \in \{1, 2, \cdots, n - 1\}, Q_{i+1} \neq P_{Q_i}$$$. Output the number modulo $$$998244353$$$.

The first line contains one integer $$$n\,(1\le n\le 10^5)$$$, denoting the size of given permutation.

The second line contains $$$n$$$ integers $$$P_1, P_2, \cdots, P_n\,(1\le P_i \le n)$$$, denoting the given permutation.

It is guaranteed that $$$\{P_1, P_2, \cdots, P_n\} = \{1, 2, \cdots, n\}$$$.

Output one line containing one integer, denoting the answer number modulo $$$998244353$$$.

4
3 4 1 2

8

The 8 permutations are:

• $$$\{1, 2, 3, 4\}$$$
• $$$\{1, 4, 3, 2\}$$$
• $$$\{2, 1, 4, 3\}$$$
• $$$\{2, 3, 4, 1\}$$$
• $$$\{3, 2, 1, 4\}$$$
• $$$\{3, 4, 1, 2\}$$$
• $$$\{4, 1, 2, 3\}$$$
• $$$\{4, 3, 2, 1\}$$$