Problem Statement

You are given an integer $N$. An integer sequence $x=(x_1,x_2,\cdots,x_N)$ of length $N$ is called a good sequence if and only if the following conditions are satisfied:

• Each element of $x$ is an integer between $1$ and $N$, inclusive.
• For each integer $i$ ($1 \leq i \leq N$), there is no position in $x$ where $i$ appears $i+1$ or more times in a row.

You are given an integer sequence $A=(A_1,A_2,\cdots,A_N)$ of length $N$. Each element of $A$ is $-1$ or an integer between $1$ and $N$. Find the number, modulo $998244353$, of good sequences that can be obtained by replacing each $-1$ in $A$ with an integer between $1$ and $N$.

Constraints

• $1 \leq N \leq 5000$
• $A_i=-1$ or $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 \cdots A_N

Output

Print the answer.