Club Schedule

Interview

Time limit1sMemory limit128 MB

Summary

Count attendance and key-passing schedules over N days where each day's leader attends and the key stays with attendees.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics
Solved: No attempts yet

Problem

Three members J, O, I attend club activities for $N$ days. Each day has 8 attendance patterns. J starts with the key. The daily leader must attend, some attendee must hold the key, and someone present takes the key home. Count valid schedules modulo 10007.

Input

Line 1: $N$ . Line 2: length- $N$ leader string over J, O, I.

Output

Print the count modulo 10007.

Examples2

Example 1
Input
```
2
OI
```
Expected output
```
7
```
Example 2
Input
```
20
JIOIJOIJOJOIIIOJIOII
```
Expected output
```
4976
```