题目背景

翻译自 CSES-2187 题。

题目描述

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

输入格式

第一行包含一个整数 $n$。

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

输出格式

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

样例

6
(()

2

提示

有两种可能的有效括号序列：

• $(())()$
• $(()())$

数据范围

• $1 \le k \le n \le 10^6$