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

题目背景

IOI 高级中学的编程俱乐部有 3 名成员：J 、O 和 I 。

最近他们正在努力制定俱乐部活动计划。

现在他们想安排 $ N $ 天的活动。 每个活动日有 $ 2 $ 种可能的日程安排，每个成员有 $ 2 $ 种（参加或不参加活动）的选择，整个俱乐部共有 $ 8 $ 种选择。 但是俱乐部活动室的钥匙只有 $1$ 把，最初由 $ J $ 持有。 在每个活动日，参加当天活动的任何 $ 1 $ 名俱乐部成员都必须带着钥匙，活动结束后，参加活动的一名俱乐部成员带着钥匙返回。

现在需要你事先确定每个活动日的负责人，以确保每个活动日都开展活动。 负责人必须始终参加当天的活动。

题目要求

给定你需要安排的天数和每个活动日负责人的信息，你需要编写一个程序，找出能让俱乐部活动在所有活动日可能进行的时间表余数，除以 $10007$。 但是，在分会活动结束时，拿回钥匙的分会成员可以是参加当天活动的任何分会成员，（也就是说） 任何人都可以在分会活动的最后一天拿回钥匙。

---

输入由 $ 2 $ 行组成。

第 $ 1 $ 行包含 $ 1 $ 个整数 $ N $ ($ 2\ \leqq\ N\ \leqq\ 1000 $)，代表我们要安排的天数。

第 $2$ 行包含一个由 $ N $ 字符组成的字符串，代表每个活动日的负责人。 这个字符串的第 $ i $ 个字符（$ 2\ \leqq\ N\ \leqq\ 1000 $）代表第 $ i $ 天活动日的负责人。 也就是说，$ i $ 字符 $J$ 、$O$ 和 $I$ 分别表示 $ i $ 日活动日的负责人是$J$ 、$O$ 和 $I$。

用 $ 1 $ 行输出除以 $ 10007 $ 的余数。

---

在样例 $ 1 $ 中， 第 $ 1 $ 天的负责人是 $O$ 先生，第 $I$ 天的负责人是 I 先生。 有 $ 7 $ 个可能的计划满足问题描述的条件。（见表）
在这个表格中，$ J $、$ O $ 和 $ I $ 分别表示 J、O 和 I 当天的参与情况。 注意，J 和 O 都必须参加第 $ 1 $ 天的活动，因为是 O 负责 $ 1 $ 天的活动，但先拿到钥匙的是 J。 还要注意的是，必须至少有 $ 1 $ 人在第 $ 1 $ 天和第 $ 2 $ 天都参加活动，因为在第 $ 1 $ 天拿着钥匙回来的人也必须在第 $ 2 $ 天参加活动。

---

示例解释 2

在输入输出示例 $ 2 $ 中，一共有 $ 72 $ 个可能的时间表满足条件。 输出除以 $ 10,007 $ 得到的余数 $ 4,976 $.