Bracket Sequences II

题目描述

你的任务是计算当给定一个序列的前缀时，长度为 n 的有效括号序列的数量。

输入格式

第一行输入一个整数 n。 第二行是一个长度为 k 的字符串：序列的前缀。

输出格式

输出序列数量对 $10^9+7$ 取模的结果。

6
(()

2

提示

$1 \le k \le n \le 10^6$ 样例解释：有两种可能的序列：$(())()$ 和 $(()())$。

标签: CSES2187|数学

来源

CSES2187|数学