문제 번호 6134 --동아리의 계획표 (部活のスケジュール表)

6134: 동아리의 계획표 (部活のスケジュール表)

시간 제한: 1 Sec  메모리 제한: 128 MB
제출: 0  해결 문제 수: 0
[제출][채점상황][게시판][:]

문제 설명

번역 : 경남과학고 29기 도회린
오번역이나 문제에 관한 질문은 게시판을 이용해주세요.

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

앞으로 N일 동안의 동아리 활동 계획표를 짜려고 한다. 각 동아리 활동 날마다 각 부원들은 참가 여부를 결정할 수 있다. 동아리실의 열쇠는 1개뿐이고, 처음에는 J군이 가지고 있었다. 각 활동을 시작할 때, 그 날의 활동에 참가하는 부원 중 적어도 한 명은 열쇠를 가지고 있어야 하며, 활동이 끝나면 활동에 참가한 부원 중 한 명이 열쇠를 가지고 돌아간다.

프로그래밍부에서는 동아리 활동 날마다 그 날의 책임자를 선정하여, 반드시 그 날의 활동에 출석하도록 정했다.

동아리 활동 날짜와 그 날의 책임자가 누구인지에 대한 정보가 주어졌을 때, 작성될 수 있는 총 N일 동안의 활동 계획표의 종류 수를 10007로 나눈 나머지를 구하는 프로그램을 작성하여라. , 동아리 활동 마지막 날에는 아무나 열쇠를 가지고 돌아가도 괜찮다.

입력

입력은 두 줄로 이루어진다.

첫째 줄에는 앞으로의 동아리 활동 날짜를 나타내는 정수 N(2 이상 1000 이하)이 주어진다.
둘째 줄에는 각 활동의 책임자를 나타내는 N자리의 문자열이 주어진다. 이 문자열의 i번째 글자는 i번째 활동 날짜의 책임자를 나타낸다.

출력

짤 수 있는 계획표의 종류를 10007로 나눈 나머지를 하나의 정수로 출력하라.

입력예시

<예시 1>
2
OI

<예시 2>
20
JIOIJOIJOJOIIIOJIOII

출력예시

<출력 예시 1>
7

<출력 예시 2>
4976

도움말

출처

[제출][채점상황]