问题

IOI 高校的编程部有三个成员：J、O 和 I。编程部正在安排社团活动的日程。

现在，他们想要安排进行为期 N 天的活动。对于每一天的活动日程，每个成员都有两种选择参加还是不参加，因此共有 8 种可能性。部室只有一把钥匙，最初由 J 持有。每一天的活动中，必须有一个参加活动的成员持有钥匙，并且活动结束后，参加活动的成员之一将带着钥匙回家。

编程部规定，为了确保每一天都有活动进行，必须提前确定每一天的负责人。负责人必须参加当天的活动。

给定活动天数以及每一天的负责人信息，请编写一个程序计算满足条件的所有可能的日程表数量并将其除以 10007 取余数。

输入

输入包含两行。

第一行包含一个整数 N (2 ≤ N ≤ 1000)，表示活动天数。

第二行包含长度为 N 的字符串，用于表示每一天的负责人。第 i 个字符（1 ≤ i ≤ N）为 'J'、'O' 或 'I'，分别表示第 i 天的活动负责人是 J 同学、O 同学或 I 同学。

输出

输出一个整数，表示满足条件的日程表数量除以 10007 的余数。

示例 1

2
OI

输出示例 1

7

对于输入示例 1，考虑为期 2 天的活动日程。第一天的负责人是 O，第二天的负责人是 I。满足问题描述条件的日程表有 7 种可能性。

在这个表格中，J、O 和 I 分别代表 J 同学、O 同学和 I 同学参加当天活动的情况。第一天的负责人是 O，但最开始持有钥匙的是 J，因此要注意第一天的活动需要 J 和 O 同时参加。此外，持有钥匙回家的人必须参加第二天的活动，因此要注意如果没有人同时参加第一天和第二天的活动，则无法满足条件。

示例 2

20
JIOIJOIJOJOIIIOJIOII

输出示例 2

4976

对于输入示例 2，满足条件的日程表总共有 72,493,594,992 种可能性。计算该数量除以 10007 的余数，结果为 4,976。