GB(Good Bye)
시간 제한2초메모리 제한1024 MB
B와 G로 이루어진 공 배열에서 색이 번갈아 나타나는 네 공을 임의로 제거할 때 도달할 수 있는 최종 배열의 가짓수를 센다.
문제
서로 다르게 생긴 공 개가 파란색(B) 또는 초록색(G)으로 칠해져 일렬로 나열되어 있다. 다음과 같은 연산을 제한 없이 수행할 수 있을 때 최종 공들의 배열로 가능한 경우의 수를 로 나눈 나머지를 출력하여라.
- 공 4개의 색이 왼쪽부터 순서대로 보았을 때 (B, G, B, G) 이거나 (G, B, G, B)인 경우, 해당 공들을 제거한다. 이때 공들이 연속해 있을 필요는 없다.
공이 하나도 제거되지 않거나, 모든 공이 제거된 경우도 하나의 경우로 센다.
입력
첫 번째 줄에 공들의 색깔을 나타내는 G와 B로 이루어진 길이 인 문자열이 주어진다.
출력
첫 번째 줄에 경우의 수를 로 나눈 나머지를 출력한다.