동아리 활동 스케줄표

문제

IOI 고등학교의 프로그래밍 부에는 J 군, O 군, I 군의 3명의 부원이 있다. 프로그래밍 부에서는 동아리 활동 스케줄을 짜려고 한다.

지금 N일간의 활동 스케줄을 정하려고 한다. 각 활동일의 스케줄로 생각할 수 있는 것은 각 부원마다 활동에 참가하는지 여부의 2가지가 있으므로, 동아리 전체로는 전부 8가지이다. 동아리방의 열쇠는 단 1개뿐이며, 처음에는 J 군이 가지고 있다. 각 활동일에는 그날의 활동에 참가하는 부원 중 누군가 1명이 열쇠를 가지고 있어야 하며, 활동이 끝난 후에는 참가한 부원 중 누군가가 열쇠를 가지고 돌아간다.

프로그래밍 부에서는 활동일에 매번 반드시 활동이 이루어지도록, 미리 각 활동일의 책임자를 정해 두었다. 책임자는 반드시 그날의 활동에 출석해야 한다.

스케줄을 정하려고 하는 날수와 각 활동일의 책임자가 누구인지에 대한 정보가 주어졌을 때, 모든 활동일에 동아리 활동을 할 수 있는 스케줄표로 생각할 수 있는 것의 개수를 10007로 나눈 나머지를 구하는 프로그램을 작성하시오. 단, 동아리 활동이 끝났을 때 열쇠를 가지고 돌아가는 부원은 그날의 활동에 참가한 부원 중 누구여도 되며, 마지막 날은 누가 열쇠를 가지고 돌아가도 된다.

입력

입력은 2개의 줄로 이루어진다.

1번째 줄에는 스케줄을 정하려고 하는 날수를 나타내는 1개의 정수 N (2 ≦ N ≦ 1000) 이 쓰여 있다.

2번째 줄에는 각 활동일의 책임자를 나타내는 N개의 문자로 이루어진 문자열이 쓰여 있다. 이 문자열의 i번째 문자 (1 ≦ i ≦ N) 는 i일째 활동일의 책임자를 나타낸다. 즉, i번째 문자가 J, O, I인 것은 각각 i일째 활동일의 책임자가 J 군, O 군, I 군임을 의미한다.

출력

스케줄표로 생각할 수 있는 것의 개수를 10007로 나눈 나머지를 1개의 줄에 출력한다.

예제 입력 1

2
OI

예제 출력 1

7

예제 1에서는 2일간의 활동일의 스케줄을 생각한다. 1일째의 책임자는 O 군, 2일째의 책임자는 I 군이다. 문제의 조건을 만족하는 스케줄표는 7가지를 생각할 수 있다.

이 표에서 J, O, I는 각각 그날에 J 군, O 군, I 군이 참가함을 나타낸다. 1일째의 책임자는 O 군이지만 처음에 열쇠를 가지고 있는 것은 J 군이므로, 1일째의 활동에는 J 군과 O 군 양쪽이 모두 참가해야 함에 주의하라. 또한 1일째에 열쇠를 가지고 돌아간 사람은 2일째에도 참가해야 하므로, 1일째와 2일째 양쪽에 모두 참가하는 사람이 적어도 1명 존재해야 함에 주의하라.

예제 입력 2

20
JIOIJOIJOJOIIIOJIOII

예제 출력 2

4976

예제 2에서는 조건을 만족하는 스케줄표가 전부 72493594992가지 있다. 그것을 10007로 나눈 나머지인 4976을 출력한다.