H. Help Me to Get This Published
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

A Gallai coloring of a complete graph on $$$n$$$ nodes is a coloring of its edges, in which the following condition holds:

  • There is no triangle whose edges are colored in $$$3$$$ distinct colors.

The color degree $$$d(v)$$$ of node $$$v$$$ is defined as the number of different colors that appear on the edges incident to $$$v$$$. Let's call sequence $$$(a_1, a_2, \ldots, a_n)$$$ a valid degree sequence if there exists some Gallai coloring of a complete graph on $$$n$$$ nodes, in which $$$d(i) = a_i$$$ for all $$$1 \le i \le n$$$.

You are given some values of $$$a_i$$$, and some are equal to $$$-1$$$. Find the number of ways to replace elements of $$$a$$$, equal to $$$-1$$$, to obtain a valid degree sequence. As this number may be large, output it modulo $$$998244353$$$.

Input

The first line of the input contains a single integer $$$n$$$ ($$$2 \le n \le 100$$$).

The second line of the input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n-1$$$, or $$$a_i = -1$$$). If $$$a_i \neq -1$$$, its value is given.

Output

Output a single integer  — the number of ways to replace elements of $$$a$$$, equal to $$$-1$$$, to obtain a valid degree sequence, modulo $$$998244353$$$.

Examples
Input
2
1 -1
Output
1
Input
3
-1 -1 -1
Output
4
Input
6
5 -1 -1 -1 -1 -1
Output
120
Note

In the first sample, the only valid degree sequence is $$$(1, 1)$$$.

In the second sample, the only valid degree sequences are $$$(1, 1, 1), (1, 2, 2), (2, 1, 2), (2, 2, 1)$$$, where the first one corresponds to the case, when all edges have the same color, and the next three correspond to the cases, when some two edges have the same color.