괄호 복구

여는 괄호 (와 닫는 괄호 )로 이루어진 문자열 $S$가 있다. 이때 다음 조건을 만족하는 문자열 $T$의 개수를 구하려고 한다.

• 조건 1. $T$는 여는 괄호와 닫는 괄호로 이루어진 길이 $L$인 문자열이다.
• 조건 2. $S$의 문자들과 $T$의 문자들을 각각 내부에서의 순서를 유지하면서 합쳐서 올바른 괄호 문자열이 되게 할 수 있다.

예를 들어, $S$ = (()이고 $L = 3$일 때 $T$ = ))(이면 1, 2, 6번째 문자를 $S$의 문자로 하고 3, 4, 5번째 문자를 $T$의 문자로 하여 (())()를 만들 수 있으므로 $T$는 조건을 만족한다.

그러나 $S$ = )()이고 $L = 3$일 때 $T$ = )((이면 $S$와 $T$를 합쳐 올바른 괄호 문자열을 만들 수 없으므로 $T$는 조건을 만족하지 않는다.

조건을 만족하는 $T$의 개수가 많아질 수 있으므로, $10^9+7$로 나눈 나머지를 구한다.

첫 번째 줄에 문자열 $S$가 주어진다. $S$는 길이가 1 이상 3,000 이하이며 (와 )로만 구성되어 있다. 두 번째 줄에 자연수 $L$ ($1 \le L \le 3{,}000$)이 주어진다.

첫 번째 줄에 문제의 정답을 출력한다.

위 입력 예제의 경우, 조건을 만족하는 $T$는 ())와 )()의 2가지가 가능하다.