D. Divine Music
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Henrique and Juliana are a sertanejo duo from Panteão Olímpico Lírico dos Imortais (POLI), which goal was to create divine music to honor the gods. The score of a divine music is a sequence of notes represented by only the numbers 0, 1 and 2. Also, it is such that the sum of every three consecutive numbers is equal to 3.

Nowadays, an old score of the famous duo was found, but some of its notes were blurred. Hence, Pedro, the musician, was commissioned to recover the original score. Pedro is afraid that this work may not be possible: it could exist more than one divine music score such that, if some of their notes were blurred, would be equal to the found score.

Tormented by that possibility, Pedro asks you to count the number of distinct divine music scores that could be the one originally written by the sertanejo duo. Notice that the answer to this question could be 0.

Input

The first line of the input has only one integer $$$n$$$ ($$$3 \leq n \leq 10^6$$$), the number of notes in the score.

The second line contains $$$n$$$ integers $$$d_i$$$ ($$$-1 \leq d_i \leq 2$$$ for every $$$1 \leq i \leq n$$$), the notes of the score. The integer -1 represents a blurred note.

Output

Print one integer: the number of distinct divine music scores that could be the one originally written by Henrique and Juliana.

Examples
Input
5
0 -1 1 -1 2
Output
1
Input
5
-1 -1 2 -1 -1
Output
2