1197: 스탬프 랠리

KOI 상점가에는 큰 길을 따라 N개의 가게가 있으며, KOI 상점가의 입구에서 출구로 향하는 각각의 가게에는 1부터 N까지의 번호가 매겨져 있습니다. KOI 상점가는 일방통행이며, 입구에서 출구 방향으로만 이동할 수 있습니다.

마을 활성화를 위해, KOI 상점가에서 스탬프 랠리를 개최하기로 결정했습니다. 이 스탬프 랠리에서 각 가게는 K, O, I 중 하나의 스탬프를 준비하고, 가게에서 물건을 구매한 사람은 스탬프 카드에 스탬프를 찍어 받습니다. 스탬프 랠리에 참여하는 사람은 정확히 3개의 가게에 들어갑니다. 상점가의 입구에서는 3칸짜리 스탬프 카드를 나눠주고, 1번째로 들어간 가게, 2번째로 들어간 가게, 3번째로 들어간 가게의 스탬프를 찍어 받습니다. 상점가의 출구에서 스탬프 카드를 회수하고, 찍힌 스탬프가 먼저 들어간 가게의 것부터 순서대로 K, O, I가 되어 있는 경우, 출구에서 상품권을 받을 수 있는 캠페인을 진행하기로 했습니다. 찍힌 스탬프의 종류나 순서가 다를 경우 상품권을 받을 수 없습니다.

이미 N개의 모든 가게가 어떤 스탬프를 준비할지 결정했지만, 새로운 가게를 KOI 상점가에 내보내기로 결정했습니다. 새 가게를 내보내는 위치는 가게 i와 가게 i+1 사이(1 ≦ i ≦ N-1), 입구와 가게 1 사이, 가게 N과 출구 사이 중 하나로 결정하며, 새 가게의 스탬프는 K, O, I 중 하나로 결정합니다.

상품권을 받을 수 있는 가게를 선택하는 방법의 수가 많을수록 스탬프 랠리가 활성화될 것이라고 상점가는 생각했습니다. 따라서, 새로운 가게의 위치와 준비할 스탬프를 결정했을 때, 위의 가게 선택 방법의 수의 최대값을 구하고 싶습니다.

KOI 상점가에 이미 있는 가게가 준비한 스탬프의 정보가 주어졌을 때, 새로운 가게의 위치와 준비할 스탬프를 결정했을 때, 상품권을 받을 수 있는 가게를 선택하는 방법의 수의 최대값을 구하는 프로그램을 작성하십시오.

첫 번째 줄에는 정수 N이 포함되어 있습니다. 이는 현재 KOI 상점가에 N개의 가게가 있다는 것을 의미합니다.
두 번째 줄에는 N개의 문자로 구성된 문자열 S가 포함되어 있습니다. 문자열 S의 왼쪽에서 i번째 문자(1 ≦ i ≦ N)는 가게 i가 준비한 스탬프의 종류를 나타냅니다.

최대 상품권을 받을 수 있는 가게 선택 방법의 수를 한 줄에 출력하십시오.

이때, 최대 상품권을 받을 수 있는 가게 선택 방법의 수가 32비트 부호 있는 정수의 범위에 들어갈 것을 보장하지 않는다는 점에 유의하십시오.

5
KOIOI

6