题目描述

译自 JOISC 2018 Day3 T3「防犯ゲート / Security Gate」

你知道「净是一些鬼畜发明公司」（Just Odd Inventions Co., Ltd.）吗？这家公司就是发明一些鬼畜玩意的。现在我们就叫它 JOI 公司。

为了防止机密信息泄露，公司门口装有一个安全门。进出这家公司必须通过这个门，并且每次只能容纳一人通过，无法两人或多人同时通过。

一旦有人通过这个安全门，安全门就会记录一条信息，表示行人是进入公司还是离开公司。公司的一名雇员 IOI 君得到了某天安全门的一份记录。我们用一个括号序列 $S$ 代表这份记录，用 $S_i$ 表示 $S$ 的第 $i$ 个字符。若 $S_i=$ (，则第 $i$ 个通过安全门的人进入了公司；若 $S_i=$ )，则第 $i$ 个通过安全门的人离开了公司。已知在当天开始和结束时，公司内都没有人。注意：存在字符串 $S$ 只包含 ( 和 ) 但不表示一个合法记录。如：这样的两份记录：())( 和 (() 就不是合法记录。第一条记录会导致 JOI 公司内有负数个人，第二条记录表示这天下班之后 JOI 公司还有一个人。

IOI 君检查完 $S$ 后，$S$ 就被病毒修改了！经过一些调查，他猜测病毒修改 $S$ 的方法如下：

• 先将「$S$ 里面连续的一段字符串」中每一个 ( 修改为 )，每一个 ) 则修改为 (。用 $S'$ 表示这次修改后的字符串。注意，该操作可能并没有执行，因此有可能出现 $S'=S$ 的情况。
• 然后将 $S'$ 中的某些字符改为 x。用 $S''$ 表示这次修改后的字符串。该操作也可能并没有执行，因此有可能出现 $S''=S'$ 的情况。

IOI 君不记得 $S$ 了，所以他想将 $S''$ 恢复到 $S$。为了达到这个目的，他首先想知道有多少可能的 $S'$（注意，不是 $S$）。

任务

给出字符串 $S''$，写一个程序计算有多少可能的 $S'$ 字符串，模 $10^9+7$ 输出。

输入格式

从标准输入中读取以下内容：

• 第一行包含一个正整数 $N$。表示 $S''$ 的长度，即两次修改后的字符串长度为 $N$。
• 第二行包含一个字符串 $S''$，每个字母都是 (，)，x 中的一个。表示修改两次之后的字符串 $S''$。

输出格式

输出一行到标准输出，输出包含 $S'$ 的可能数量，对 $10^9+7$ 取模后输出。如果没有这样的字符串，输出 $0$。

4
x))x

3

10
xx(xx()x(x

45

5
x))x(

0

10
xxxxxxxxxx

684

数据范围与提示

对于所有数据，满足 $1\le N\le 300$。

本题共有 $5$ 个子任务。每个子任务的分数和附加限制如下：