{"raw_statement":[{"iden":"problem statement","content":"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:\n\n*   Each element of $x$ is an integer between $1$ and $N$, inclusive.\n*   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.\n\nYou 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$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 5000$\n*   $A_i=-1$ or $1 \\leq A_i \\leq N$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $A_2$ $\\cdots$ $A_N$"},{"iden":"sample input 1","content":"2\n-1 -1"},{"iden":"sample output 1","content":"3\n\nYou can obtain four sequences by replacing each $-1$ with an integer between $1$ and $2$.\n$A=(1,1)$ is not a good sequence because $1$ appears twice in a row.\nThe other sequences $A=(1,2),(2,1),(2,2)$ are good.\nThus, the answer is $3$."},{"iden":"sample input 2","content":"3\n2 -1 2"},{"iden":"sample output 2","content":"2"},{"iden":"sample input 3","content":"4\n-1 1 1 -1"},{"iden":"sample output 3","content":"0"},{"iden":"sample input 4","content":"20\n9 -1 -1 -1 -1 -1 -1 -1 -1 -1 7 -1 -1 -1 19 4 -1 -1 -1 -1"},{"iden":"sample output 4","content":"128282166"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}