Colorful Parentheses Subsequences

A bracket sequence is a string consisting of the two characters ( and ). A well‐formed (or good) bracket sequence can be defined recursively as follows:

• The empty string is a good bracket sequence.
• If S is a good bracket sequence then (S) is also good. In this case the two brackets added are said to be a matching pair.
• If S and T are good bracket sequences then their concatenation ST is also good.

A colored bracket sequence is a bracket sequence in which every bracket is painted in a specific color. We say that a colored bracket sequence is a rainbow sequence if it satisfies all of the following conditions:

• When ignoring the colors (i.e. only taking the bracket symbols into account) the sequence is a good bracket sequence.
• Every two adjacent brackets in the sequence have different colors.
• For every matching pair of brackets, the colors of the two brackets are different.

We say that a sequence T can be selected from a string S if one or more characters from S can be picked (in the same order as in S) to form T. Given a colored bracket sequence P, your task is to count how many different rainbow bracket sequences can be selected from P. Note that even if two sequences have the same bracket structure, they are considered different if the colors differ; similarly, if the same sequence can be obtained by different selections, it is counted only once.

You are required to implement the following function:

int count(vector P)

Here, the vector P represents the colored bracket sequence. For each index i, if P[i] < 0 it denotes a left bracket and if P[i] > 0 it denotes a right bracket. In both cases, |P[i]| gives the color of that bracket. The function should return the number of rainbow bracket sequences that can be selected from P, modulo 1000000007.

Note: Your submitted code should not perform any input or output operations.

inputFormat

The function will receive a single argument:

• vector<int> P: an array representing a colored bracket sequence. A negative value indicates a left bracket, and a positive value indicates a right bracket. The absolute value corresponds to the color of the bracket.

outputFormat

Return an integer representing the number of distinct rainbow bracket sequences (as defined) that can be selected from P, modulo 1000000007.

sample

-1 1

0