Problem Statement

For a permutation $P = (P_1, \ldots, P_N)$ of $(1, \ldots, N)$, let $P' = (P'_1, \ldots, P'_N)$ be the permutation obtained by performing the following operation once.

• For $i = 1, 2, \ldots, N-1$ in this order, if $P_i > P_{i+1}$, swap $P_i$ and $P_{i+1}$.

You are given a sequence $Q = (Q_1, \ldots, Q_N)$ of length $N$. Each $Q_i$ is $-1$ or an integer between $1$ and $N$, inclusive.

Find the number, modulo $998244353$, of permutations $P$ of $(1, \ldots, N)$ such that, for every $i$, if $Q_i \neq -1$ then $Q_i = P'_i$.

Constraints

• All input numbers are integers.
• $2 \leq N \leq 5000$
• Each $Q_i$ is $-1$ or an integer between $1$ and $N$.
• Each of $1,2,\ldots,N$ appears at most once in $Q$.

Input

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

N
Q_1 \ldots Q_N

Output

Print the answer.