题目描述

你听说过 Just Odd Inventions Co., Ltd. 吗？这家公司的业务是做“奇思妙想的发明”。我们姑且称它为 JOI 公司。

为了防止机密信息泄露，JOI 公司的大门安装了一道安全门。任何人进出公司都必须通过这道门，且同一时间不可能有两人或以上同时通过。

每当有人通过这道门时，系统会记录此人是进入还是离开公司。现在，JOI 公司的员工 IOI-kun 保留了某一天的门禁记录。该记录由字符串 $S$ 表示：若 $S$ 的第 $i$ 个字符为 ‘(’，则表示第 $i$ 个通过门的人是进入公司；若为 ‘)’，则表示第 $i$ 个通过门的人是离开公司。IOI-kun 知道，在这一天开始和结束时，公司内均无人。请注意，存在一些仅由 ‘(’ 和 ‘)’ 组成的字符串无法表示合法记录：例如，记录不能是 ‘)(’ 或 ‘((’，因为前者意味着公司内人数曾为负数，后者意味着在当天结束时公司内仍有人员。

下一刻，IOI-kun 检查记录时，发现字符串 $S$ 已被传播至 JOI 公司的计算机病毒修改！经过调查，他推测修改过程如下：

• 首先，$S$ 中的某一段连续子串被修改：对于该子串中的每个字符，若原字符为 ‘(’，则变为 ‘)’；若原字符为 ‘)’，则变为 ‘(’。我们将修改后的字符串记为 $S'$。被修改的子串长度可能为 0，即 $S = S'$。
• 接着，$S'$ 中的 0 个或更多字符变为 ‘x’。我们将此次修改后的字符串记为 $S''$。

IOI-kun 已不记得原始字符串 $S$，因此他试图从 $S''$ 恢复 $S$。为此，他首先希望统计所有可能成为 $S'$（注意不是 $S$，请小心）的字符串的数量。

任务

给定字符串 $S''$，编写一个程序，计算所有可能成为 $S'$ 的字符串的数量，结果对 $1\,000\,000\,007$ 取模。

输入格式

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

• 输入的第一行包含一个整数 $N$。这表示修改后的字符串 $S''$ 的长度为 $N$。
• 输入的第二行包含一个字符串 $S''$，其中每个字符为 ‘(’、‘)’ 或 ‘x’。这表示修改后的字符串是 $S''$。

输出格式

向标准输出写入一行。输出应包含所有可能成为 $S'$ 的字符串的数量，结果对 $1\,000\,000\,007$ 取模。若不存在这样的字符串，输出 $0$。

4
x))x

3

10
xx(xx()x(x

45

5
x))x(

0

10
xxxxxxxxxx

684

提示

数据范围

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

• $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 分]

无额外约束。

翻译由 Qwen3-235B 完成