JOI 2013/2014 예선 4- 강의실 관리 (Class) > 문제은행 : 정보올림피아드&알고리즘




2828 : 강의실 관리 (Class)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
10 회   
시도횟수
21 회   

문제

경비원 세경이와 세운이, 그리고 세일이가 N일 동안 강의실을 관리하려고 한다. 빌딩 주인이 N일 동안 총책임자 한 명을 배정해놓았으며, 그 사람은 그날 꼭 출근해야 한다.

 

 또, 강의실 열쇠를 갖고 있는 사람도 꼭 출근해야 한다. 처음에는 세경이가 강의실 열쇠를 갖고 있으며, 퇴근할 때 열쇠를 다른 사람(그날 출근한 경비원 중 한 명)에게 양도할 수 있다. 3명의 경비원들은 총책임자 표를 보고 매일 누가 출근할지 표를 작성하려고 한다. 처음에는 세경이가 강의실 열쇠를 갖고 있으므로 첫 날에는 세경이는 반드시 출근해야 한다. 또, 열쇠 관리를 수월하게 하기 위하여 각 날마다 출근한 사람 중 적어도 한 명은 다음 날에도 출근해야 한다.

 

위 조건을 모두 만족하면서 출근표를 제작할 때, 표를 제작하는 방법의 수를 구하는 프로그램을 작성하여라.

 

 


* 입력 예 1에 대한 보충 설명

 

가능한 경우는 아래 표와 같이 7가지 있다.


 


입력형식

첫 번째 줄에는 날의 수 N이 주어진다. (2 ≤ N ≤ 1,000) 두 번째 줄에는 각 날마다 총책임자의 이름이 주어진다. 'K'는 세경, 'O'는 세운, 'I'는 세일이를 의미한다.

출력형식

출근표를 제작하는 방법의 수를 10,007로 나눈 나머지를 출력한다.

입력 예

2
OI

출력 예

7

입력 예

20
KIOIKOIKOKOIIIOKIOII

출력 예

4976


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP