해석

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

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