문제 - Coding is fun

시간	메모리	제출 회	올바른 답 회	비율
1초	64MB	35	7	20.0%

나의 횟수	나의 최근 판정	시도 명	성공 명	비율
		7	5	71.4%

동아리 스케쥴

KOI 고등학교 정보 동아리에는 3명의 학생 K, O, I가 있다. 정보 동아리는 다가오는 한국정보올림피아드에서 좋은 점수를 받기 위해 N일의 스터디 모임 일정을 계획하려고 한다. 1명의 학생이 하나의 스터디 모임에 대해 참여, 또는 불참 2가지 경우가 있으므로 3명의 학생이 하나의 스터디 모임에 참여하는 경우의 수는 총 8가지다.

스터디 모임을 하기 위한 동아리실의 열쇠는 1개 뿐이며 맨 처음은 K군이 열쇠를 갖고 있기 때문에 첫날 모임의 동아리실은 K군이 열어야 한다. 모임을 마치고 집으로 돌아갈 때는 그날 모임에 참석한 학생 중 한 명이 열쇠를 가지고 동아리실 문을 닫고 집으로 간다. 따라서 그 다음날 동이리 모임을 위해서는 전 날에 열쇠를 가져간 학생이 반드시 참석해서 동아리실 문을 열어야 스터디 모임을 할 수 있다. 단, 마지막 날은 누가 열쇠를 가져가도 상관없다. 또한 N일 동안 스터디 모임이 반드시 이루어지도록 하기 위해 N일 모두 1명의 책임자가 배정되어 있으며 책임자는 그날 혼자라도 동아리실에 나와서 스터디 모임을 해야 한다.

동아리 스터디 모임의 날짜 수 N과 각 날짜의 책임자가 주어질 때 가능한 모든 경우의 일정의 개수를 10007로 나눈 나머지를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 동아리 스터디 모임의 날짜 수 N(2<=N<=1,000)이 주어진다. 두 번째 줄에는 각 날짜의 책임자를 나타내는 문자열이 주어진다. 이 문자열의 i 번째 문자 (1 ≦ i ≦ N)는 i 일째 활동 날짜의 책임자를 나타내며, 책임자는 K, O, I 중 하나다. 즉, i 번째 문자가 K라면 i 일째 활동 날짜의 책임자가 K군임을 의미한다.

※ 예시 1 : 1일째의 책임자는 O군, 2일째의 책임자는 I군일 때, 2일간의 모든 경우의 일정을 고려하면 다음의 표와 같다. 총 7가지 경우의 일정이 가능하므로 7을 출력한다.

가능한 일정	1일째	2일째
일정1	K, O	O, I
일정2	K, O	K, I
일정3	K, O	K, O, I
일정4	K, O, I	I
일정5	K, O, I	K, I
일정6	K, O, I	O, I
일정7	K, O, I	K, O, I

※ 예시2 : 가능한 경우의 수가 72493594992이므로, 10007로 나눈 나머지 4976을 출력한다.

출력
첫 번째 줄에 가능한 모든 경우의 일정의 개수를 10007로 나눈 나머지를 출력한다.

예시
1	입력	2 OI
1	출력	7
2	입력	20 KIOIKOIKOKOIIIOKIOII
2	출력	4976

문제

LOGIN