括号串是由两种字符 ( 或 ) 构成的字符串。

良好的括号串 是可以通过以下规则构造的括号串：

• 空字符串是良好的括号串。
• 如果 $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]|$ 的值区分。
• 该函数需要返回：从给定的染色括号串中可以取出的五彩缤纷括号串的数量，对 $1\ 000\ 000\ 007$ 取模。

在你提交的源代码的任何部分都不允许执行输入输出函数。

样例数据

样例 1

用 $p_c$ 表示颜色为 $c$ 的括号 $p$。

给定染色括号串 $(_1)_2(_3)_3(_1)_2$

评测程序将如下调用函数：

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

可以取出的五彩缤纷括号串共有以下 6 种：

• $(_1)_2$
• $(_1)_3$
• $(_3)_2$
• $(_1)_2(_1)_2$
• $(_1)_2(_3)_2$
• $(_1)_3(_1)_2$

因此，count 函数应返回 6。

某个特定字符串的取出方式可能有多种，例如在本例中，$(_1)_2$ 有 3 种取法。

样例 2

给定染色括号串 $(_1)_6(_3(_6)_1(_1)_3)_6$

评测程序将如下调用函数：

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

可以取出的五彩缤纷括号串共有 21 种，因此 count 函数应返回 21。

此时，$(_1(_3)_3)_6$ 或 $(_6(_1)_3)_6$ 也可以被取出，并且从括号形态上看是良好的括号串，但由于分别存在相邻括号颜色相同、以及配对括号颜色相同的情况，因此它们不是五彩缤纷的括号串。

样例 3

给定染色括号串 $(_7(_1)_4(_1)_2)_6(_3)_4)_7(_5)_6(_2)_6)_5)_7$

评测程序将如下调用函数：

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

count 函数应返回 1116。

限制

• 设 $P$ 的长度为 $N$，则 $1 \le N \le 700$。
• $1 \le |P[i]| \le N$（对所有 $0 \le i \le N-1$）。

子任务

1. （5 分）$N \le 20$
2. （30 分）$N \le 200$
3. （27 分）$N \le 500$，且 $|P[i]| \le 20$
4. （14 分）$|P[i]| \le 2$
5. （24 分）无额外限制

Sample grader

Sample grader 的输入格式如下：

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

Sample grader 的输出格式如下：

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