部活 스케줄

면접 대비

시간 제한1초메모리 제한128 MB

요약

매일 리더가 출석하고 열쇠는 출석자 사이에서만 이동하도록 N일간의 출석과 열쇠 전달 경우의 수를 10007로 나눈 나머지를 구합니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 조합론
정답자: 아직 제출이 없습니다

문제

J, O, I 세 명이 $N$ 일 동안 매일 부활동을 한다. 각 날 참가 여부는 8가지이며, 처음에 J가 열쇠를 가진다. 매일 책임자는 반드시 참가하고, 참가자 중 누군가가 열쇠를 가져야 하며, 활동 후 참가자가 열쇠를 가져간다. 조건을 만족하는 스케줄 수를 10007로 나눈 나머지를 출력한다.

입력

첫 줄에 $N$ ( $2 \le N \le 1000$ ). 둘째 줄에 길이 $N$ 의 책임자 문자열 (J, O, I).

출력

가능한 스케줄 수를 10007로 나눈 나머지를 출력한다.

예제2

예제 1
입력
```
2
OI
```
예상 출력
```
7
```
예제 2
입력
```
20
JIOIJOIJOJOIIIOJIOII
```
예상 출력
```
4976
```