시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 6 5 5 83.333%

문제

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 行で出力せよ.

예제 입력

2
OI

예제 출력

7

예제 입력 2

20
JIOIJOIJOJOIIIOJIOII

예제 출력 2

4976

힌트