15943번 - parentheses recover

여는 괄호 ’(’와 닫는 괄호 ’)’로 이루어진 문자열 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⁹+7로 나눈 나머지를 계산하도록 한다.

첫 번째 줄에 문자열 S가 주어진다. S는 길이가 1 이상 3,000 이하이며 ‘(‘와 ‘)’로만 구성되어있다.

두 번째 줄에 자연수 L(1 ≤ L ≤ 3,000)이 주어진다.

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

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