서로 다른 올바른 괄호 부분 문자열 세기

올바른 괄호 문자열은 다음과 같이 재귀적으로 정의된다.

• 빈 문자열 ""는 올바른 괄호 문자열이다.
• $X$와 $Y$가 올바른 괄호 문자열이면 $XY$도 올바른 괄호 문자열이다.
• $X$가 올바른 괄호 문자열이면 $(X)$도 올바른 괄호 문자열이다.
• 올바른 괄호 문자열은 모두 위 규칙으로 만들 수 있다.

"()", "()()()", "(()())", "(((())))"는 모두 올바른 괄호 문자열이다.

문자열 $T$가 문자열 $S$의 부분 문자열이라는 말은, $S$에서 문자 몇 개를 지워서 $T$를 만들 수 있다는 뜻이다. 하나도 지우지 않거나 전부 지워도 된다. 남은 문자의 순서는 바꾸지 않는다. 예를 들어 "bdf"는 "abcdefg"의 부분 문자열이다.

'('와 ')'로만 이루어진 문자열 $S$가 주어진다. $S$의 비어 있지 않은 부분 문자열 중에서 서로 다른 올바른 괄호 문자열이 몇 개인지 구하는 프로그램을 작성하시오. 지운 위치가 달라도 같은 문자열이 되면 하나로 센다.

첫째 줄에 문자열 $S$가 주어진다. $S$는 '('와 ')'로만 이루어져 있고, 길이는 $1$ 이상 $100$ 이하이다.

첫째 줄에 $S$의 비어 있지 않은 부분 문자열 중에서 서로 다른 올바른 괄호 문자열의 개수를 1,000,000,007로 나눈 나머지를 출력한다.