Description

Aob and Blice are playing a game.

There is a permutation $p$ of length $n$, and both Aob and Blice each hold an initially empty distinct set, denoted as $S_A$ and $S_B$ respectively. The rules for one round of the game are as follows:

• First, Aob randomly selects two integers $x$ and $y$ such that $1 \leq x < y \leq n$ and $p_x > p_y$. Then, Aob randomly chooses one of the two ordered pairs $(x, y)$ or $(p_x, p_y)$ to add to his set $S_A$.

• After that, Blice must choose one of the pairs $(y, x)$ or $(p_y, p_x)$ to add to her set $S_B$. Note that $x$ and $y$ are the same as those chosen by Aob in the previous step.

After infinitely many rounds $^{\dagger}$, Aob and Blice will compare their sets. Although Aob plays randomly, Blice is smarter and hopes to make both sets exactly the same in the end, so the game will end in a tie—this way, neither of them will be upset!

Unfortunately, some elements in the permutation have disappeared. Blice has asked for your help to determine how many possible original permutations could allow them to achieve a tie after infinitely many rounds. For convenience, you only need to compute the answer modulo $998244353$.

$^{\dagger}$ A tie after infinitely many rounds is defined as follows: for any $\varepsilon > 0$, there exists a positive integer $N$ such that for all $n > N$, Blice can adopt a strategy ensuring that the probability of not achieving a tie after $n$ rounds is less than $\varepsilon$.

Input Format

The first line contains a positive integer $n$.

The second line contains $n$ integers $p_i$. For each $i$, if $p_i = 0$, it indicates that the number at the $i$-th position has disappeared; otherwise, it represents the number that was originally at the $i$-th position in the permutation.

Output Format

Output a single line containing an integer that represents the answer modulo $998244353$.

3
0 2 0

2

7
0 3 2 0 5 7 0

2

Hint

Sample $1$ Explanation

Exactly two permutations are valid: $\{1,2,3\},\{3,2,1\}$.

Subtasks and Constraints

• Special Property A: $p_i \ne 0$.
• Special Property B: $p_i = 0$.

For all tests, it is guaranteed that:

• $1 \le n \le 10^6$;
• $0 \le p_i \le n$;
• For all $1 \le i < j \le n$, if $p_i \ne 0$ and $p_j \ne 0$, then $p_i \ne p_j$.