問題

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$ 行で出力せよ．

入力例 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$ において，条件をみたすスケジュール表は全部で $72\\,493\\,594\\,992$ 通り考えられる．それを $10\\,007$ で割った余りである $4\\,976$ を出力する．