시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB188514141.837%

문제

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

  • 빈 문자열 ""는 올바른 괄호 문자열이다.
  • "X"와 "Y"가 올바른 괄호 문자열이라면, "XY"도 올바른 괄호 문자열이다.
  • "X"가 올바른 괄호 문자열이라면, "(X)"도 올바른 괄호 문자열이다.
  • 모든 올바른 괄호 문자열은 위의 규칙을 이용해서 만들 수 있다.

올바른 괄호 문자열은 "", "()", "()()()", "(()())", "(((())))" 와 같은 문자열이다.

문자열 T가 문자열 S의 부분 문자열이 되려면, S에서 일부 문자(전체나 없을 수도 있다)를 지워서 T를 만들 수 있어야 한다. 예를 들어, "bdf"는 "abcdefg"의 부분 문자열이다.

'('와 ')'로만 이루어진 괄호 문자열 S가 주어진다. S의 비어있지 않은 부분 문자열 중에서 서로 다른 올바른 괄호 문자열의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 문자열 S가 주어진다. S는 '('와 ')'로만 이루어져 있으며, 길이는 100보다 작거나 같은 자연수이다.

출력

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

예제 입력 1

(())(

예제 출력 1

2

예제 입력 2

())

예제 출력 2

1

예제 입력 3

)(((

예제 출력 3

0

힌트

예제 1의 경우에 만들 수 있는 올바른 괄호 문자열은 ()와 (()) 이다.

예제 2의 경우에는 ()만 만들 수 있다.

출처