해석

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

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$로 나눈 나머지를 출력하시오.