题目描述

从前有个括号序列 $\red{s，}$满足 $\red{|s| = m}$。

你需要统计括号序列对 $\red{(p, q) }$的数量。

其中 $\red{(p, q) }$满足 $\red{|p| + |s| + |q| = n，}$且 $\red{p + s + q }$是一个合法的括号序列。

输入格式

从文件 $\red{bracket.in }$中读入数据。

第一行两个正整数 $\red{n, m}$。

第二行一个长度为 $\red{m }$的括号序列，表示 $\red{s}$。

输出格式

输出到文件 $\red{bracket.out }$中。

输出一行一个整数，表示符合条件的 $\red{(p, q) }$的数量对 $\red{10^9 + 7 }$取模的值。

样例

输入样例1

4 1 (

输出样例1

4

输入样例2

4 4 (())

输出样例2

1

输入样例3

4 3 (((

输出样例3

0

提示

数据

对于 $\red{10\% }$的数据，$\red{n ≤}$ $\red{20}$；

对于 $\red{25\% }$的数据，$\red{n ≤}$ $\red{200}$；

对于另外 $\red{5\% }$的数据，$\red{n = m}$；

对于 $\red{55\% }$的数据，$\red{n - m ≤}$ $\red{200}$；

对于 $\red{100\% }$的数据，$\red{1 ≤}$ $\red{m ≤}$ $\red{n ≤}$ $\red{10^5, n - m ≤}$ $\red{2000}$。