5613：[GESP202609七级] 括号序列
文件提交：无需freopen
内存限制：128 MB
时间限制：1.000 S
评测方式：普通裁判
金币值：
命题人：
提交：0
解决：0
题目描述
## 题目背景
2026 年 09 月 GESP C++ 七级编程第 2 题
## 题目描述
对于字符串 $S$ 与 $T$，如果从 $S$ 中删除任意多个字符可以得到 $T$，那么 $T$ 是 $S$ 的子序列。换言之，$T$ 是选取 $S$ 中的若干字符按下标顺序连接而成的。两个子序列不同当且仅当所选取的下标不同。
例如 `sun` 是 `sequence` 的子序列，因为从 `sequence` 中删除 `eq`、`e` 和 `ce` 可以得到 `sun`；`sequence` 有 $2^8$ 个不同的子序列，其中有空字符串，也有三个不同的子序列 `e`，因为 `sequence` 的第 $2,5,8$ 个字符都为 `e`，分别保留这三个字符得到的子序列是不同的。
对于字符串 $S$，如果 $S$ 满足以下条件那么 $S$ 是合法括号序列：
- $S$ 是空字符串，或者
- $S$ 可由 `(`、合法括号序列、`)` 三者连接得到，或者
- $S$ 可由两个合法括号序列连接得到。
例如 `()`、`()()`、`(())` 和 `(()())` 都是合法括号序列。但是 `(()`、`)(` 不是合法括号序列。
给定一个长度为 $n$ 的仅包含 `(` 与 `)` 的字符串 $S$。请你求出 $S$ 所有 $2^n$ 个子序列中有多少个合法括号序列。由于答案可能很大，请你输出答案对 $10^9$ 取模的结果。
例如，$S$ 为 `))(()(` 时共有 $3$ 个子序列是合法括号序列，分别为空字符串与两个不同的子序列 `()`。
## 输入格式
第一行，一个正整数 $n$，表示字符串 $S$ 的长度。
第二行，长度为 $n$ 的仅包含 `(` 与 `)` 的字符串 $S$。
## 输出格式
输出一行，一个整数，表示 $S$ 的合法括号子序列的数量对 $10^9$ 取模的结果。
## 样例
```input1
6
))(()(
```
```output1
3
```
```input2
34
((((((((((((((((()))))))))))))))))
```
```output2
333606220
```
## 数据范围
对于 $40\%$ 的测试点，保证 $1\le n\le 400$。
对于所有测试点，保证 $1\le n\le 2000$。