注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 17 及以上）

请在提交源代码前添加 #include "colorful.h"。

题目描述

题目译自 2022년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T2 「알록달록한 괄호열」

括号序列是由两种字符 ( 和 ) 组成的字符串。好的括号序列可以通过以下规则构成：

• 空字符串是好的括号序列。
• 如果 $S$ 是好的括号序列，那么 $(S)$ 也是好的括号序列。在这种情况下，$S$ 两端的括号是配对的。
• 如果 $S$ 和 $T$ 都是好的括号序列，那么 $ST$ 也是好的括号序列。

彩色括号序列是指每个括号都被涂上特定颜色的括号序列。五彩缤纷的括号序列需要满足以下所有条件：

• 忽略颜色，仅看括号的形式时是好的括号序列。
• 所有相邻的两个括号颜色不同。
• 所有配对的两个括号颜色不同。

当从字符串 $S$ 中选出一个或多个字符按顺序排列成 $T$ 时，称可以从 $S$ 中选出 $T$。给定一个彩色括号序列，问可以从中选出多少个五彩缤纷的括号序列？即使括号形式相同，但只要颜色不同就算作不同情况；即使选取方式不同，但结果相同也只算作一种情况。

实现细节

你需要实现以下函数：

int count(vector<int> P)

• 该函数只会被调用一次。
• P：表示彩色括号序列，$P[i]$ 表示第 $i$ 个括号的信息。$P[i] < 0$ 表示左括号，$P[i] > 0$ 表示右括号，$|P[i]|$ 的值表示颜色。
• 该函数需要返回从给定彩色括号序列中可以选出的五彩缤纷括号序列的数量，并对 $1000000007$ 取模。

注意，提交的代码中不应包含任何输入输出操作。

样例 1

用颜色 $c$ 涂的括号 $p$ 表示为 $p$。给定彩色括号序列 $\underset{123312}{()()()}$，评测程序会调用如下函数：

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

可以选出的五彩缤纷括号序列有 $\underset{12}{()},\underset{13}{()},\underset{32}{()},\underset{1212}{()()},\underset{1232}{()()},\underset{1312}{()()}$ 共 $6$ 种。因此，调用的 count 函数应返回 6。

从中选取特定字符串的方法有多种，在这个样例中，选取 $\underset{12}{()}$ 的方法有 $3$ 种。

样例 2

给定彩色括号序列 $(()())$，评测程序会调用如下函数：

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

可以选出的五彩缤纷括号序列有 $\underset{13}{()},\underset{16}{()},\underset{31}{()},\underset{36}{()},\underset{61}{()},\underset{63}{()},\underset{1313}{(())},\underset{1316}{(())},\underset{1613}{(())},\underset{1616}{(())},\underset{1636}{(())},\underset{3136}{(())},\underset{3616}{(())},\underset{3636}{(())},\underset{1613}{()()},\underset{1616}{()()},\underset{1631}{()()},\underset{1636}{()()},\underset{163136}{()(())},\underset{163616}{()(())},\underset{163636}{()(())}$ 共 $21$ 种。因此，调用的 count 函数应返回 21。

$\underset{1336}{(())}$ 和 $\underset{6136}{(())}$ 虽然括号序列是好的，但由于相邻两个括号颜色相同或配对括号颜色相同，因此不是五彩缤纷的括号序列。

样例 3

给定彩色括号序列 $\underset{714126347562657}{(()())())()()))}$，评测程序会调用如下函数：

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

调用的 count 函数应返回 1116。

数据范围与提示

对于所有输入数据，满足：

• 用 $N$ 表示 $P$ 的长度，$1 \leq N \leq 700$
• 对于所有 $i$ $(0 \leq i \leq N-1)$，$1 \leq |P[i]| \leq N$

详细子任务附加限制及分值如下表所示。

示例评测程序

示例评测程序的输入格式如下：

• 第 $1$ 行：$N$
• 第 $2$ 行：$P[0]\,P[1]\,\cdots\,P[N-1]$

示例评测程序的输出格式如下：

• 第 $1$ 行：count 函数返回的值