B. Strange Permutations
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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

Input

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

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

Example
Input
4
3 4 1 2
Output
8
Note

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\}$$$