즐거운 간식 시간이다.

당신은 간식 묶음을 쪼개서 아이들에게 나누어 주어야 한다.

간식 묶음은 끈의 형태, 즉 문자열로 나타나 있으며 간식은 I,C,P만 존재한다(Injulmi, Cookie, Patbingsu)

여기서 당신은 문자열 끈의 일부분을 잘라 모든 부분 묶음이 맛있는 간식 묶음만 존재하도록 만들고 싶다.

맛있는 간식 묶음의 조건은 다음과 같다.

[ 맛있는 간식 묶음 : I,C,P 세 문자 중 두 문자의 등장 횟수가 동일해야 하며(0회 가능), 나머지 한 문자는 더 많이 등장해야 한다. ]

(예를 들어 ICPC는 맛있는 간식 묶음이다. C가 2번 등장하고, I와 P는 같은 횟수로 1번씩 등장하기 때문이다.

또한 PPPP도 맛있는 간식 묶음이다. P가 4번 등장하고, I와 C는 같은 횟수로 0번씩 등장하기 때문이다.

그러나 PIC, PIPCCC는 맛있는 간식 묶음이 아니다. )

I,C,P로 이루어진 문자열을 적절히 잘라 모든 부분 묶음이 맛있는 간식 묶음이 되는 방법의 수를 구하라.

간식 시간 timer 6s memory 1024MB

간식 시간 6s 1024MB