PinkRabbit is a rabbit.

To maintain his perfect physique, PinkRabbit goes for a run every day. The place where he runs can be abstracted as a directed graph with $n$ nodes, where each node has a color (black or white), and edges only exist from a node with a smaller index to a node with a larger index.

Every time he runs, PinkRabbit chooses a path in the graph as his running route. This path must satisfy the condition that adjacent nodes have different colors. Specifically, a single node also counts as a path. At the same time, PinkRabbit has two forms: human form and rabbit form. When PinkRabbit finishes running a path, his form toggles (human becomes rabbit, rabbit becomes human).

To keep his perfect physique, PinkRabbit will run through all distinct valid paths on this graph.

Now, the colors of some nodes in this directed graph are already determined, while the colors of other nodes can be either black or white. Also, for all $1 \le i < j \le n$, a directed edge from $i$ to $j$ in this graph may or may not exist.

PinkRabbit starts in human form. You need to find the number of different valid graphs such that PinkRabbit is in rabbit form after running through all the paths. You only need to output the result modulo $998,244,353$.

Two graphs are different if and only if there exists a node $i$ such that its color is different in the two graphs, or there exists a pair $(i, j)$ such that one graph has a directed edge from $i$ to $j$ while the other does not.

Input

The first line contains a positive integer $n$.

The second line contains $n$ integers, where the $i$-th integer is $1$ if the color of node $i$ is black, $0$ if the color of node $i$ is white, and $-1$ if it is undetermined.

Output

Output a single integer representing the answer.

Examples

Input 1

3
-1 0 1

Output 1

6

Note 1

There are 6 valid configurations: (1) Node 1 is black, edge set is $\{<1, 3>\}$ (2) Node 1 is black, edge set is empty (3) Node 1 is white, edge set is empty (4) Node 1 is white, edge set is $\{<1, 2>\}$ (5) Node 1 is white, edge set is $\{<1, 3>, <2, 3>\}$ (6) Node 1 is white, edge set is $\{<1, 2>, <1, 3>, <2, 3>\}$

Input 2

5
-1 0 0 -1 1

Output 2

2112

Input 3

10
0 0 1 1 -1 -1 1 0 1 0

Output 3

142536119

Subtasks

Subtask 1 (10 points): $n \le 5$; Subtask 2 (30 points): $n \le 50$; Subtask 3 (10 points): $n \le 150$; Subtask 4 (15 points): $n \le 500$; Subtask 5 (15 points): $n \le 5000$; Subtask 6 (20 points): No special restrictions.

All data satisfies $1 \le n \le 2 \times 10^5$.