시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB291978338.073%

문제

$($와 $)$로만 이루어진 문자열을 괄호 문자열이라고 한다. 괄호 문자열 중, 다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 한다.

  1. 빈 문자열은 올바른 괄호 문자열이다.
  2. $A$가 올바른 괄호 문자열이라면, $( A )$도 올바른 괄호 문자열이다. 이때 생성되는 괄호 쌍을 서로 매칭된다고 표현한다.
  3. $A$와 $B$가 올바른 괄호 문자열이라면, $AB$도 올바른 괄호 문자열이다.

방에 들어가려다가 가방에 들어가 버린 승재는 올바른 괄호 문자열을 암호화했다.

열고 닫는 매칭되는 괄호 쌍이 01 또는 10으로 암호화됐다. 예를 들어 (()) 는 0011, 0101, 1010, 1100으로 암호화될 수 있다. 반면, 1001로 암호화될 수는 없다. 첫 번째 괄호와 마지막 괄호가 매칭되는데 11이기 때문이다. 암호화된 문자열이 주어졌을 때, 가능한 올바른 괄호 문자열의 개수를 출력하시오. 값이 너무 클 수 있으니 $10^9 + 7$로 나눈 나머지를 출력하시오.

입력

첫 줄에 0과 1로만 이루어진 문자열 S가 주어진다. $( 2 \le |S| \le 300 )$

출력

첫 줄에 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력하시오.

예제 입력 1

1001

예제 출력 1

1

예제 입력 2

001011

예제 출력 2

2

001011를 해석하는 경우 중 한 가지는 ((()))이다.

출처

University > 경인지역 6개대학 연합 > shake! 2021 D번