Problem Description

The programming club at IOI High School has three members: J-kun, O-kun, and I-kun. They are trying to create a schedule for their activities over the next $N$ days.

For each day of activity, there are $8$ possible schedules as each member can either attend or not attend the activity. There is only one key to the club room, and initially, J-kun holds it. Each activity day requires that one of the members attending that day has the key, and after the activity, one of the attendees can take the key home.

The club has appointed a responsible member for each activity day, who must attend the activity on that day.

Given the number of days $N$ and the responsible member for each day, create a program that calculates the number of possible schedules that allow all activities to take place, modulo $10,007$. Note that any member attending the activity can take the key home after the activity, and it does not matter who takes the key home on the last day.

Input Format

The input consists of two lines.

The first line contains a single integer $N$ ($2 \leq N \leq 1000$), representing the number of days for which the schedule is being made.

The second line contains a string of $N$ characters, where the $i$-th character ($1 \leq i \leq N$) represents the responsible member for the $i$-th day. Specifically, 'J', 'O', and 'I' mean that J-kun, O-kun, and I-kun are responsible, respectively.

Output Format

Output a single line with the number of possible schedules, modulo $10,007$.

Sample Input and Output

Sample Input #1

2
OI

Sample Output #1

7

Sample Input #2

20
JIOIJOIJOJOIIIOJIOII

Sample Output #2

4976

Notes/Hints

Sample Explanation 1

In Sample Input #1, consider the schedule for the two days. The responsible members are O-kun on the first day and I-kun on the second day. There are 7 possible schedules that meet the conditions. Note that since J-kun initially has the key, both J-kun and O-kun must attend the first day's activity. Also, at least one person who attends both days must exist so that the key can be passed on.

Sample Explanation 2

In Sample Input #2, there are a total of $72,493,594,992$ possible schedules that meet the conditions. Output the remainder when this number is divided by $10,007$, which is $4,976$.

见题面 Input 部分

见题面 Output 部分