你知道 Just Odd Inventions Co., Ltd. 吗？这家公司的业务是做“纯粹古怪的发明”。在这里，我们简称为 JOI 公司。

JOI 公司的门口安装了一个安全门，以防止机密信息泄露。进出公司时必须通过该门。不可能有两个人同时通过该门。

每当有人通过此门时，它都会记录下该人是进入还是离开公司的信息。现在，JOI 公司的一名员工 IOI 君拥有某一天该门的记录。该记录由字符串 $S$ 表示：如果 $S$ 的第 $i$ 个字符是 ‘(’，则意味着第 $i$ 个通过该门的人进入了公司；如果 $S$ 的第 $i$ 个字符是 ‘)’，则意味着第 $i$ 个通过该门的人离开了公司。IOI 君知道，在这一天的开始和结束时，公司内部都没有人。注意，存在仅由 ‘(’ 和 ‘)’ 组成的字符串不能代表有效的记录：例如，记录不能是 ()) ( 或 (()，因为这分别意味着公司内部的人数变成了负数，或者在一天结束时公司内还有人。

随后，IOI 君检查了记录，发现字符串 $S$ 被在 JOI 公司内传播的计算机病毒修改了！经过调查，他推测修改过程如下：

• 首先，字符串 $S$ 的一个连续片段发生了如下变化：对于片段中的每个字符，如果是 ‘(’ 则变为 ‘)’，如果是 ‘)’ 则变为 ‘(’。我们将此变化后的字符串记为 $S'$。变化片段的长度可能为 0，即 $S = S'$。
• 然后，$S'$ 中的 0 个或多个字符变成了 ‘x’。我们将此变化后的字符串记为 $S''$。

IOI 君不记得 $S$ 了，所以他试图从 $S''$ 恢复 $S$。为此，他首先想计算有多少种字符串可能是 $S'$（注意，不是 $S$）。

题目描述

给定字符串 $S''$，编写一个程序，计算有多少种字符串可能是 $S'$，结果对 $1\,000\,000\,007$ 取模。

输入格式

从标准输入读取以下数据。

• 第一行包含一个整数 $N$。这意味着修改后的字符串 $S''$ 的长度为 $N$。
• 第二行包含一个字符串 $S''$，每个字符都是 ‘(’、‘)’ 或 ‘x’。这意味着修改后的字符串为 $S''$。

输出格式

输出一行到标准输出。输出应包含可能是 $S'$ 的字符串数量，对 $1\,000\,000\,007$ 取模。如果没有这样的字符串，输出 0。

数据范围

所有输入数据满足以下条件：

• $1 \le N \le 300$。

子任务

共有 5 个子任务。各子任务的分数和附加限制如下：

• 子任务 1 [4 分]：$N \le 100$，$S''$ 中 ‘x’ 的数量最多为 4。
• 子任务 2 [8 分]：$N \le 100$，$S''$ 中 ‘x’ 的数量最多为 12。
• 子任务 3 [18 分]：$N \le 100$，$S''$ 中 ‘x’ 的数量最多为 20。
• 子任务 4 [43 分]：$N \le 100$。
• 子任务 5 [27 分]：无附加限制。

样例

样例输入 1

4
x))x

样例输出 1

3

说明 1

在样例 1 中，$S' = )))( $ 是不可能的，因为不存在可以作为 $S$ 的字符串。 以下三个字符串可以是 $S'$： $S' = ()(($。例如，考虑 $S = ()()$。 $S' = ())) $。例如，考虑 $S = ()()$。 * $S' = )))) $。例如，考虑 $S = (()) $。 由于只有这些字符串可以是 $S'$，输出 3。

样例输入 2

10
xx(xx()x(x

样例输出 2

45

样例输入 3

5
x))x(

样例输出 3

0

样例输入 4

10
xxxxxxxxxx

样例输出 4

684