题目描述

给定一个只由左括号 ( 和右括号 ) 组成的字符串 (S)。

请计算满足以下条件的字符串 (T) 的数量：

1. (T) 是一个只由左括号和右括号组成、长度为 (L) 的字符串；
2. 可以将 (S) 中的字符与 (T) 中的字符交错合并，在分别保持它们内部字符相对顺序不变的前提下，得到一个合法括号序列。

换言之，合并过程中需要使用 (S) 和 (T) 的所有字符，并且：

• (S) 中各字符的相对顺序不能改变；
• (T) 中各字符的相对顺序不能改变。

一个括号字符串是合法括号序列，当且仅当：

• 从左到右扫描时，任意前缀中的左括号数量都不少于右括号数量；
• 整个字符串中的左括号数量与右括号数量相等。

例如，当

[ S=\texttt{(()},\qquad L=3 ]

且

[ T=\texttt{))(} ]

时，可以令合并后字符串的第 (1,2,6) 个字符来自 (S)，第 (3,4,5) 个字符来自 (T)，从而得到：

(())()

这是一个合法括号序列，因此该字符串 (T) 满足条件。

但是，当

[ S=\texttt{)()},\qquad L=3 ]

且

[ T=\texttt{)((} ]

时，无论怎样交错合并 (S) 和 (T)，都无法得到合法括号序列，因此该字符串 (T) 不满足条件。

对于同一个字符串 (T)，即使存在多种合法的交错合并方式，也只将其计数一次。

由于答案可能很大，请输出答案对 (1,000,000,007) 取模后的结果。

输入格式

第一行输入一个只由 ( 和 ) 组成的字符串 (S)。

第二行输入一个整数 (L)。

输出格式

输出满足条件的字符串 (T) 的数量，对 (1,000,000,007) 取模。

数据范围

[ 1\le |S|\le 3000 ]

[ 1\le L\le 3000 ]

样例输入

(
3

样例输出

2

样例说明

长度为 (3) 且满足条件的字符串 (T) 共有两个：

())
)()

对于 (T=\texttt{())})，可以将 (S) 中的左括号插入最前面，得到合法括号序列：

(())

对于 (T=\texttt{)()})，也可以将 (S) 中的左括号插入最前面，得到合法括号序列：

()()

因此答案为 (2)。