# KOITST 22 Colorful Brackets

https://www.acmicpc.net/problem/25021

You have some sequence $S$ consisting of some ‘(’ and ‘)’, where each bracket has a color.

Find the number of ways to choose a (not neccesarily contiguous) subsequence $T$ of $S$, modulo $10^9+7$, that satisfies the following conditions:

- $T$ is a valid bracket sequence
- Two adjacent brackets in $T$ have different colors
- Two matching brackets in $T$ have different colors

Two subsequences are different if at any position, the color or (open or close) is different. Meaning two subsequences extracted in different ways count as the same way if the extracted sequence is the same. Refer to sample 1 for more details.

## Implementation

You must implement the following function.

`int count(vector<int> P)`

This function is called only once.

$P$: Represents a 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 should return the number of colorful parenthesis sequences that can be extracted from the given colored parenthesis sequence modulo $1,000,000,007$.

No input/output functions should be executed in any part of the submitted source code.

## Constraints

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


## Examples

### Example 1

A colored parenthesis p painted with color c is represented as $\underset{c}{p}$.

Given the colored parenthesis sequence $\underset{1}{(} \underset{2}{)} \underset{3}{(} \underset{3}{)} \underset{1}{(} \underset{2}{)}$, the grader calls the function as follows:

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

The colorful parenthesis sequences that can be extracted from here are $\underset{1}{(} \underset{2}{)}$, $\underset{1}{(} \underset{3}{)}$, $\underset{3}{(} \underset{2}{)}$, $\underset{1}{(} \underset{2}{)} \underset{1}{(} \underset{2}{)}$, $\underset{1}{(} \underset{2}{)} \underset{3}{(} \underset{2}{)}$, $\underset{1}{(} \underset{3}{)} \underset{1}{(} \underset{2}{)}$, totaling $6$ possibilities. Therefore, the called count function should return $6$.

There may be multiple ways to extract a specific string, and in this example, there are 3 ways to extract $\underset{1}{(} \underset{2}{)}$.

## Example 2

Given the colored parenthesis sequence $\underset{1}{(} \underset{6}{)} \underset{3}{(} \underset{6}{(} \underset{1}{)} \underset{1}{(} \underset{3}{)} \underset{6}{)}$, the grader calls the function as follows:

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

The colorful parenthesis sequences that can be extracted from here are 
, totaling $21$ possibilities. Therefore, the called count function should return $21$.

## Example 3

Given the colored parenthesis sequence $\underset{7}{(} \underset{1}{(} \underset{4}{)} \underset{1}{(} \underset{2}{)} \underset{6}{)} \underset{3}{(} \underset{4}{)} \underset{7}{)} \underset{5}{(} \underset{6}{)} \underset{2}{(} \underset{6}{)} \underset{5}{)} \underset{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 called count function should return $1116$.