#2839. 「JOISC 2018 Day 3」安全门

内存限制:1024 MiB 时间限制:5000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: HeRaNO

题目描述

译自 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

样例

样例输入 1

4
x))x

样例输出 1

3

样例说明 1

在样例 1 中, S'=\texttt{)))(} 是不可能的,因为这样的话就没有能为 S 的字符串了。

以下三个字符串可能为 S'

  • S'=\texttt{())(} ,考虑 S=\texttt{()()}
  • S'=\texttt{()))} ,考虑 S=\texttt{()()}
  • S'=\texttt{))))} ,考虑 S=\texttt{(())}

因为只有这些字符串能为 S' ,所以输出 3

样例输入 2

10
xx(xx()x(x

样例输出 2

45

样例输入 3

5
x))x(

样例输出 3

0

样例输入 4

10
xxxxxxxxxx

样例输出 4

684

数据范围与提示

对于所有数据,满足 1\le N\le 300

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

Subtask 附加限制 分数
1 N\le 100 S'' 中字符 x 的数量最多为 4 4
2 N\le 100 S'' 中字符 x 的数量最多为 12 8
3 N\le 100 S'' 中字符 x 的数量最多为 20 18
4 N\le 100 43
5 无附加限制 27