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

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

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

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

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

入力は，\(2\) 行からなる．

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

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

スケジュール表として考えられるものの数を \(10\,007\) で割った余りを \(1\) 行で出力せよ．

JOI 2014 · JCIOI · CC BY-SA 4.0