NC53249. 安全门
描述
译自 JOISC 2018 Day3 T3「防犯ゲート / Security Gate」
你知道「净是一些鬼畜发明公司」（JustOddInventionsCo.,Ltd.）吗？这家公司就是发明一些鬼畜玩意的。现在我们就叫它JOI公司。
为了防止机密信息泄露，公司门口装有一个安全门。进出这家公司必须通过这个门，并且每次只能容纳一人通过，无法两人或多人同时通过。
一旦有人通过这个安全门，安全门就会记录一条信息，表示行人是进入公司还是离开公司。公司的一名雇员IOI君得到了某天安全门的一份记录。我们用一个括号序列S代表这份记录，用
表示S的第i个字符。若
(，则第i个通过安全门的人进入了公司；若)，则第i个通过安全门的人离开了公司。已知在当天开始和结束时，公司内都没有人。注意：存在字符串S只包含(和)但不表示一个合法记录。如：这样的两份记录：())(和(()就不是合法记录。第一条记录会导致JOI公司内有负数个人，第二条记录表示这天下班之后JOI公司还有一个人。
IOI君检查完S后，S就被病毒修改了！经过一些调查，他猜测病毒修改S的方法如下：
为了防止机密信息泄露，公司门口装有一个安全门。进出这家公司必须通过这个门，并且每次只能容纳一人通过，无法两人或多人同时通过。
一旦有人通过这个安全门，安全门就会记录一条信息，表示行人是进入公司还是离开公司。公司的一名雇员IOI君得到了某天安全门的一份记录。我们用一个括号序列S代表这份记录，用
IOI君检查完S后，S就被病毒修改了！经过一些调查，他猜测病毒修改S的方法如下：
- 先将「S里面连续的一段字符串」中每一个(修改为)，每一个)则修改为(。用S'表示这次修改后的字符串。注意，该操作可能并没有执行，因此有可能出现S'=S的情况。
- 然后将S'中的某些字符改为x。用S''表示这次修改后的字符串。该操作也可能并没有执行，因此有可能出现S''=S'的情况。
IOI君不记得S了，所以他想将S''恢复到S。为了达到这个目的，他首先想知道有多少可能的S'（注意，不是S）。
任务
给出字符串S''，写一个程序计算有多少可能的S'字符串，模
输出。
任务
给出字符串S''，写一个程序计算有多少可能的S'字符串，模
输入描述
从标准输入中读取以下内容：
第一行包含一个正整数N。表示S''的长度，即两次修改后的字符串长度为N。
第二行包含一个字符串S''，每个字母都是(，)，x中的一个。表示修改两次之后的字符串S''。
输出描述
输出一行到标准输出，输出包含S'的可能数量，对
示例1
输入:
4 x))x
输出:
3
说明:
在样例1中，以下三个字符串可能为S'：
因为只有这些字符串能为S'，所以输出3。
示例2
输入:
10 xx(xx()x(x
输出:
45
示例3
输入:
5 x))x(
输出:
0
示例4
输入:
10 xxxxxxxxxx
输出:
684