loj#P2839. 「JOISC 2018 Day 3」安全门

「JOISC 2018 Day 3」安全门

题目描述

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

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

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

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

IOI 君检查完 SS 后,SS 就被病毒修改了!经过一些调查,他猜测病毒修改 SS 的方法如下:

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

IOI 君不记得 SS 了,所以他想将 SS'' 恢复到 SS。为了达到这个目的,他首先想知道有多少可能的 SS'(注意,不是 SS)。

任务

给出字符串 SS'',写一个程序计算有多少可能的 SS' 字符串,模 109+710^9+7 输出。

输入格式

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

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

输出格式

输出一行到标准输出,输出包含 SS' 的可能数量,对 109+710^9+7 取模后输出。如果没有这样的字符串,输出 00

4
x))x
3
10
xx(xx()x(x
45
5
x))x(
0
10
xxxxxxxxxx
684

数据范围与提示

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

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

Subtask 附加限制 分数
11 N100N\le 100SS'' 中字符 x 的数量最多为 44 44
22 N100N\le 100SS'' 中字符 x 的数量最多为 1212 88
33 N100N\le 100SS'' 中字符 x 的数量最多为 2020 1818
44 N100N\le 100 4343
55 无附加限制 2727