D - 部活のスケジュール表 (Schedule) Editorial /

Time Limit: 10 sec / Memory Limit: 256 MB

配点: 100

問題

IOI 高校のプログラミング部には,J 君と O 君と I 君の 3 人の部員がいる. プログラミング部では,部活のスケジュールを組もうとしている.

今, N 日間の活動のスケジュールを決めようとしている. 各活動日 のスケジュールとして考えられるものは,各部員については活動に参加するかどうか の 2 通りがあり,部としては全部で 8 通りある. 部室の鍵はただ 1 つだけであり,最初は J 君が持っている. 各活動日には,そ の日の活動に参加する部員のうちのいずれか 1 人が鍵を持っている必要 があり,活動後に参加した部員のいずれかが鍵を持って帰る.

プログラミング部では,活動日には毎回必ず活動が行われるように,あらかじめ各活動日の責任者を定めた. 責任者は,必ずその日の活動に出席しなければならない.

スケジュールを決めようとしている日数と,各活動日の責任者が誰であるかの情報が与えられた時,すべての活動日に部活動を行うことができるようなスケジュール表 として考えられるものの数を 10007 で割った余りを求めるプログラムを 作成せよ. ただし,部活の終了時に鍵を持って帰る部員は,その日の活動に参加している部員の誰でもよく,最終日は誰が鍵を持って帰ってもよいものとする.


入力

入力は, 2 行からなる.

1 行目には,スケジュールを決めようとしている日数を表す 1 つの整数 N (2 \leq N \leq 1000) が書かれている.

2 行目には,各活動日の責任者を表す N 文字からなる文 字列が書かれている. この文字列の i 文字目 (1 \leq i \leq N) は, i 日目の活動日の責任者を表す. すなわち, i 文字目が J, O, I であることはそれぞれ i 日目の活動日の責任者が J 君,O 君,I 君であることを意味する.

出力

スケジュール表として考えられるものの数を 10007 で割った余りを 1 行で出力せよ.


入力例 1

2
OI

出力例 1

7

入出力例 1 において, 2 日間の活動日のスケジュールを考える. 1 日目の責任者は O 君, 2 日目の責任者は I 君 である. 問題文の条件をみたすスケジュール表は 7 通り考えられる.

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