005 - 部活のスケジュール表 (Schedule)

時間制限 8 秒 / メモリ制限 64 MB / 得点 100 / x 5 /


TLE
8sec
MLE
64MB
得点
100

問題

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 通り考えられる.

 1 日目   2 日目 
スケジュール 1    J, O O, I
スケジュール 2    J, O J, I
スケジュール 3    J, O J, O, I
スケジュール 4    J, O, I I
スケジュール 5    J, O, I J, I
スケジュール 6    J, O, I O, I
スケジュール 7    J, O, I J, O, I

この表では,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 を出力する.