A parenthesis sequence is a string consisting of two types of characters, '(' and ')'. A good parenthesis sequence is a parenthesis sequence that can be formed by the following rules: The empty string is a good parenthesis sequence. If $S$ is a good parenthesis sequence, then $(S)$ is also a good parenthesis sequence. In this case, the two parentheses attached to both ends of $S$ are said to be paired. * If $S$ and $T$ are good parenthesis sequences, then $ST$ is also a good parenthesis sequence.

A colored parenthesis sequence is a parenthesis sequence where each parenthesis is colored with a specific color. A colorful parenthesis sequence is a colored parenthesis sequence that satisfies all of the following conditions: It is a good parenthesis sequence when ignoring the colors and looking only at the shape of the parentheses. The colors of any two adjacent parentheses are different. * The colors of any two paired parentheses are different.

When string $T$ is formed by picking one or more characters from string $S$ and arranging them in their original order, we say that $T$ can be extracted from $S$. Given a colored parenthesis sequence, how many colorful parenthesis sequences can be extracted from it? There may be multiple colored parenthesis sequences with the same parenthesis shape, but if even one parenthesis has a different color, they must be considered different cases. If there are multiple ways to extract characters but the result is the same, it should be considered as one case.

Implementation Details

You must implement the following function:

int count(vector<int> P)

• This function is called exactly once.
• $P$: Represents the colored parenthesis sequence, where $P[i]$ represents the information of the $i$-th parenthesis. If $P[i] < 0$, it represents '(', and if $P[i] > 0$, it represents ')'. The color is distinguished by the value of $|P[i]|$.
• This function must return the number of colorful parenthesis sequences that can be extracted from the given colored parenthesis sequence, modulo $1\,000\,000\,007$.

You must not execute any input/output functions in any part of your submitted source code.

Examples

Example 1

Given the colored parenthesis sequence $(_1 )_2 (_3 )_3 (_1 )_2$, the grader calls the function as follows:

count({ -1, 2, -3, 3, -1, 2 })

The colorful parenthesis sequences that can be extracted are $(_1 )_2$, $(_1 )_3$, $(_3 )_2$, $(_1 )_2 (_1 )_2$, $(_1 )_2 (_3 )_2$, and $(_1 )_3 (_1 )_2$, totaling 6. Therefore, the count function should return 6. There can be multiple ways to extract a specific string; in this example, there are 3 ways to extract $(_1 )_2$.

Example 2

Given the colored parenthesis sequence $(_1 )_6 (_3 (_6 )_1 (_1 )_3 )_6$, the grader calls the function as follows:

count({ -1, 6, -3, -6, 1, -1, 3, 6 })

There are 21 colorful parenthesis sequences that can be extracted. Therefore, the count function should return 21. Note that $(_1 (_3 )_3 )_6$ and $(_6 (_1 )_3 )_6$ can also be extracted, and while they are good parenthesis sequences in terms of shape, they are not colorful parenthesis sequences because there are cases where two adjacent parentheses have the same color or two paired parentheses have the same color.

Example 3

Given the colored parenthesis sequence $(_7 (_1 )_4 (_1 )_2 )_6 (_3 )_4 )_7 (_5 )_6 (_2 )_6 )_5 )_7$, the grader calls the function as follows:

count({ -7, -1, 4, -1, 2, 6, -3, 4, 7, -5, 6, -2, 6, 5, 7 })

The count function should return 1116.

Constraints

• Let $N$ be the length of $P$, $1 \le N \le 700$.
• $1 \le |P[i]| \le N$ (for all $0 \le i \le N - 1$).

Subtasks

1. (5 points) $N \le 20$
2. (30 points) $N \le 200$
3. (27 points) $N \le 500$, $|P[i]| \le 20$ (for all $0 \le i \le N - 1$)
4. (14 points) $|P[i]| \le 2$ (for all $0 \le i \le N - 1$)
5. (24 points) No additional constraints.

Sample grader

The input format for the sample grader is as follows: Line 1: $N$ Line 2: $P[0] \ P[1] \ \dots \ P[N - 1]$

The output format for the sample grader is as follows: * Line 1: The value returned by the count function.