#CS2187. 括号序列 II

括号序列 II

当前没有测试数据。

题目背景

翻译自 CSES-2187 题。

题目描述

你的任务是计算在给定序列前缀的情况下，长度为 n 的有效括号序列的数量。

输入格式

第一行包含一个整数 n。

第二行包含一个长度为 k 的字符串：括号序列的前缀。

输出格式

输出有效括号序列的数量，结果对 109+710^9+7109+7 取模。

样例

6
(()

2

样例1解释 有两种可能的有效括号序列：

• (())()(())()(())()

• (()())(()())(()())

说明/提示

$1 \leq k \leq n \leq 10^6$