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

[problemUrl]: https://atcoder.jp/contests/joi2014yo/tasks/joi2014yo_d 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 $ 行で出力せよ． - - - - - -

### Sample Explanation 1 入出力例 $ 1 $ において， $ 2 $ 日間の活動日のスケジュールを考える．$ 1 $ 日目の責任者は O 君， $ 2 $ 日目の責任者は I 君である．問題文の条件をみたすスケジュール表は $ 7 $ 通り考えられる． !\[2014-yo-t4-fig01.png\](https://img.atcoder.jp/joi2014yo/2014-yo-t4-fig01.png) この表では，J，O，I はそれぞれその日に J 君，O 君，I 君が参加することを表す．$ 1 $ 日目の責任者は O 君であるが，最初鍵を持っているのは J 君であるため，$ 1 $ 日目の活動には J 君，O 君の両方が参加する必要があることに注意せよ．また，$ 1 $ 日目に鍵を持って帰った人は $ 2 $ 日目にも参加しないといけないので，$ 1 $ 日目と $ 2 $ 日目の両方に参加する人が少なくとも $ 1 $ 人存在しなければならないことに注意せよ． - - - - - - ### Sample Explanation 2 入出力例 $ 2 $ において，条件をみたすスケジュール表は全部で $ 72\,493\,594\,992 $ 通り考えられる．それを $ 10\,007 $ で割った余りである $ 4\,976 $ を出力する．