Gomory și scândurile de lemn

Gomory has just moved to the Lucky Mill. He cares a lot about the aesthetics of the fence surrounding the mill, but some planks are missing, and the remaining ones differ in height. For economic reasons, he will leave the planks that already exist in place and will only add new ones in the missing positions. Also, so that the mill does not appear too confusing to passersby, he wants a certain height to be a majority. Since Gomory is too busy counting his money, help him by counting the ways in which he can build the fence.

Task

Formally, you are given an array $h$ of length $n$ representing the heights of the planks. If a plank is missing at position $i$, then you will receive the value $-1$. Otherwise, you will receive a natural number between $1$ and $n$ representing the height of the plank at position $i$. You must output the number of ways to replace the values $-1$ in the array with natural numbers between $1$ and $n$ such that there exists a majority element.

Input Data

On the first line, a natural number $n$ is read, representing the number of planks in the fence.

On the second line, the elements of the array $h$ are read, separated by a space.

Output Data

You must output a single number representing the number of ways modulo $10^9 + 7$ in which a majority element can be obtained.

Constraints and Notes

• $1 \le n \le 200{,}000$
• $h_i = -1$ or $1 \le h_i \le n$, for any $i$ from $1$ to $n$
• An element is majority if it appears at least $\lfloor\frac{n}{2}\rfloor + 1$ times.

Example

stdin

4
1 -1 2 -1

stdout

2

Explanation

The values equal to $-1$ can be replaced with any value from $1$ to $4$. The only possibilities with a majority element are: $[1 , 1 , 2 , 1]$ and $[1 , 2 , 2 , 2]$. If we form the array $[1 , 2 , 2 , 3]$, $2$ is not a majority element because it appears fewer than $\lfloor\frac{4}{2}\rfloor + 1$ times, that is, fewer than $3$ times.