페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5104
서브태스크

동아리 활동 1초 128MB

문제

KOI 정보학교의 프로그래밍 동아리에는, K군과 O군과 I군의 3명의 부원이 있다. 

프로그래밍 동아리에서는 동아리 활동의 스케줄을 짜려고 한다.
내일부터 N일 간의 활동 일정을 결정하려고 한다. 
각 활동일의 스케줄은, 각 부원에 대해서는 활동에 참가할지 어떨지의 2 가지가 있고, 
부 전체로는 2*2*2=8 가지가 있다. 
부실의 열쇠는 단 하나뿐이며, 처음에는 K 군이 가지고 있다. 
각 활동일에는, 그 날의 활동에 참가하는 부원 중 어느 1명이 열쇠를 가지고 있어야 하고, 
활동 후에 참가한 부원 중 한 명이 열쇠를 가지고 돌아간다.
동아리에서는, 매일 반드시 활동이 행해지도록, 미리 각 활동일의 책임자를 정했다. 
책임자는 반드시 그날의 활동에 참석해야 한다.
스케줄을 결정하려고 하는 일수와, 각 활동일의 책임자가 누구인지의 정보가 주어졌을 때, 
모든 활동일에 부활동을 실시할 수 있는 스케줄 표의 수를 10007로 나눈 나머지를 찾는 프로그램을 작성하라.

마지막 날은 누구나 열쇠를 가지고 돌아갈 수 있는 것으로 한다.​

 

예로서 [입출력 예 1]을 살펴보자.

2 일간의 스케줄이 주어진다.

1 일째의 책임자는 O 군, 

2 일째의 책임자는 I 군이다. 

문제문의 조건에 따라 다음 7가지를 생각할 수 있다.

1일차     2일차

(K,O)    (O,I)

(K,O)    (K,I)

(K,O)    (K,O,I)

(K,O,I)  (I)

(K,O,I)  (K,I)

(K,O,I)  (O,I)

(K,O,I)  (K,O,I)

 

각 날짜에 K또는 O또는 I가 참여하는 것을 나타낸다.

1일째 책임자는 O군이지만, 첫 열쇠를 가지고 있는 것은 K군이기 때문에, 

첫날 활동에는 K군, O군 모두가 참가할 필요가 있다.

 

또한 1일째에 열쇠를 가지고 돌아온 사람은 2일째에도 참가해야 하기 때문에 

1일째와 2일째 모두에 참가하는 사람이 적어도 1명 존재해야 한다는 점에 주의하여라.

 


입력

입력은 두 줄로 구성된다.

첫 번째 줄에는 일정을 결정하려는 일 수를 나타내는 하나의 정수 N (2 ≤ N ≤ 1000)이 주어진다.

두 번째 줄에는 각 활동 날짜의 책임자를 나타내는 N개의 문자로 구성된 문자열이 주어진다.

이 문자열의 i번째 문자 (1 ≤ i ≤ N)는 i 일째 활동 일의 책임자를 나타낸다. 

즉, i번째 문자가  K, O, I 인 것은 각각 i 일째의 활동일의 책임자가 K군, O 군, I 군임을 의미한다.​

 

<서브태스크>

#1 (25점) : N <= 6

#2 (75점) : 추가적인 제한 조건이 없다.


출력

​가능한 스케줄 표의 수를 10007로 나눈 나머지를 한 줄에 출력하라. 


예제1

입력
2

OI
출력
7

예제2

입력
20

KIOIKOIKOKOIIIOKIOII
출력
4976

출처

JOI 2014 예선 4

역링크