짜고 치는 가위바위보 (Small)

Small 버전에서는 문자열의 길이 제한이 $20$으로 주어진다.

가위바위보 챔피언십이 열렸고 수많은 관중이 지켜보고 있다. lighter와 smallant는 이 챔피언십의 결승에 올랐다. 둘은 어릴 적부터 가장 친한 친구라 누가 이기든 별로 신경 쓰지 않는다. 그래서 두 사람은 이번 결승에서 장난을 치기로 했다.

결승은 여러 라운드의 가위바위보로 진행된다. lighter는 첫 번째 라운드를 제외하고, smallant가 바로 이전 라운드에 낸 것을 따라 낼 계획이다. 그러나 관중은 이런 장난을 싫어한다. lighter가 이긴 라운드의 바로 다음 라운드에서 비기면, 관중은 두 사람이 장난을 치고 있음을 알아채고 분노할 것이다.

관중이 분노하면 챔피언십의 후원이 끊길 수 있으므로, smallant는 무엇을 낼지 다시 생각해야 했다. 곰곰이 생각한 smallant는 원래 내려던 가위바위보 정보 중 일부분만 취하면 문제가 해결된다는 것을 알았다.

일부분만 취한다는 것은, 원래 내려던 가위바위보 정보가 문자열로 주어졌을 때 순서를 바꾸지 않고 몇 개의 문자를 제거하는 것을 뜻한다.

예를 들어 결승이 8라운드로 구성되었다고 하자. smallant는 표 1과 같이 첫 번째 라운드부터 여덟 번째 라운드까지 보, 가위, 보, 가위, 보, 보, 주먹, 가위 순서로 낼 계획이다. 이때 lighter는 첫 번째 라운드에만 주먹을 내고, 그 이후 라운드부터는 smallant를 따라 낸다.

이 경우 다섯 번째 라운드에서 lighter가 이기고 그 직후 라운드에서 비겼으므로 관중이 분노할 것이다.

따라서 이 경우에는 표 2와 같이, 원래 계획인 보, 가위, 보, 가위, 보, 보, 주먹, 가위에서 여섯 번째와 일곱 번째를 제외하고 보, 가위, 보, 가위, 보, 가위 순서로 결승을 진행하면 된다.

smallant가 내려던 가위바위보 정보가 주어졌을 때, 관중이 분노하지 않도록 그 정보의 일부분만 취하는 경우의 수를 구하시오. 단, 라운드는 최소 하나 이상 있어야 한다.