레이팅 미적용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
OI7