33545번 - GB(Good Bye)

문제

서로 다르게 생긴 공 $N$개가 파란색(B) 또는 초록색(G)으로 칠해져 일렬로 나열되어 있다. 다음과 같은 연산을 제한 없이 수행할 수 있을 때 최종 공들의 배열로 가능한 경우의 수를 10ドル^9+7$로 나눈 나머지를 출력하여라.

• 공 4개의 색이 왼쪽부터 순서대로 보았을 때 (B, G, B, G) 이거나 (G, B, G, B)인 경우, 해당 공들을 제거한다. 이때 공들이 연속해 있을 필요는 없다.

공이 하나도 제거되지 않거나, 모든 공이 제거된 경우도 하나의 경우로 센다.

입력

첫 번째 줄에 공들의 색깔을 나타내는 G와 B로 이루어진 길이 $N$인 문자열이 주어진다.

출력

첫 번째 줄에 경우의 수를 10ドル^9+7$로 나눈 나머지를 출력한다.

제한

• 1ドル\le N\le 120$

힌트