部活 스케줄

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

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

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