Score: $600$ points

问题陈述

对于一个排列 $P = (P_1, P_2, \dots, P_N)$，它是 $(1, 2, \dots, N)$ 的一个排列，我们通过以下步骤定义 $F(P)$：

• 存在一个序列 $B = (1, 2, \dots, N)$。 只要存在一个整数 $i$ 使得 $B_i < P_{B_i}$，就执行以下操作：
  • 让 $j$ 是满足 $B_i < P_{B_i}$ 的最小整数 $i$。然后，用 $P_{B_j}$ 替换 $B_j$。 定义 $F(P)$ 为这个过程结束时的 $B$。（可以证明这个过程在有限步后终止。）

给定一个长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$。有多少个排列 $P$ 满足 $F(P) = A$？求出模 $998244353$ 的结果。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

For a permutation $P = (P_1, P_2, \dots, P_N)$ of $(1, 2, \dots, N)$, we define $F(P)$ by the following procedure:

• There is a sequence $B = (1, 2, \dots, N)$.
  As long as there is an integer $i$ such that $B_i \lt P_{B_i}$, perform the following operation:
  • Let $j$ be the smallest integer $i$ that satisfies $B_i \lt P_{B_i}$. Then, replace $B_j$ with $P_{B_j}$.Define $F(P)$ as the $B$ at the end of this process. (It can be proved that the process terminates after a finite number of steps.)

You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$. How many permutations $P$ of $(1,2,\dots,N)$ satisfy $F(P) = A$? Find the count modulo $998244353$.

Constraints

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq N$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$

$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the number, modulo $998244353$, of permutations $P$ that satisfy $F(P) = A$.

Sample Input 1

4
3 3 3 4

Sample Output 1

1

For example, if $P = (2, 3, 1, 4)$, then $F(P)$ is determined to be $(3, 3, 3, 4)$ by the following steps:

• Initially, $B = (1, 2, 3, 4)$.
• The smallest integer $i$ such that $B_i \lt P_{B_i}$ is $1$. Replace $B_1$ with $P_{B_1} = 2$, making $B = (2, 2, 3, 4)$.
• The smallest integer $i$ such that $B_i \lt P_{B_i}$ is $1$. Replace $B_1$ with $P_{B_1} = 3$, making $B = (3, 2, 3, 4)$.
• The smallest integer $i$ such that $B_i \lt P_{B_i}$ is $2$. Replace $B_2$ with $P_{B_2} = 3$, making $B = (3, 3, 3, 4)$.
• There are no more $i$ that satisfy $B_i \lt P_{B_i}$, so the process ends. The current $B = (3, 3, 3, 4)$ is defined as $F(P)$.

There is only one permutation $P$ such that $F(P) = A$, which is $(2, 3, 1, 4)$.

Sample Input 2

4
2 2 4 3

Sample Output 2

0

Sample Input 3

8
6 6 8 4 5 6 8 8

Sample Output 3

18