Câu lạc bộ lập trình của trường trung học IOI có ba thành viên là J, O và I. Câu lạc bộ đang lập lịch sinh hoạt cho \(N\) ngày.

Trong mỗi ngày, mỗi thành viên có hai lựa chọn: tham gia hoặc không tham gia. Vì vậy, xét riêng việc tham gia của ba thành viên, có tất cả \(8\) khả năng cho một ngày.

Phòng câu lạc bộ chỉ có một chiếc chìa khóa, ban đầu do J giữ. Vào mỗi ngày sinh hoạt, một trong những thành viên tham gia ngày đó phải mang theo chìa khóa. Sau buổi sinh hoạt, một trong những thành viên đã tham gia sẽ mang chìa khóa về.

Để bảo đảm buổi sinh hoạt diễn ra vào tất cả các ngày đã định, câu lạc bộ chỉ định trước một người phụ trách cho mỗi ngày. Người phụ trách bắt buộc phải tham gia buổi sinh hoạt của ngày đó.

Cho số ngày cần lập lịch và người phụ trách của từng ngày, hãy viết chương trình đếm số lịch tham gia cho phép câu lạc bộ sinh hoạt vào tất cả các ngày, rồi in ra phần dư của số đó khi chia cho \(10007\).

Thành viên mang chìa khóa về sau mỗi buổi có thể là bất kỳ thành viên nào tham gia buổi đó. Vào ngày cuối cùng, ai mang chìa khóa về cũng được. Một lịch được xác định bởi những thành viên tham gia từng ngày.

Dữ liệu vào

Dữ liệu vào gồm \(2\) dòng:

• Dòng đầu tiên chứa số nguyên \(N\), là số ngày cần lập lịch.
• Dòng thứ hai chứa một chuỗi gồm \(N\) ký tự. Ký tự thứ \(i\) (\(1 \le i \le N\)) cho biết người phụ trách ngày thứ \(i\): J, O, I lần lượt tương ứng với J, O, I.

Dữ liệu ra

In ra một dòng chứa phần dư của số lịch hợp lệ khi chia cho \(10007\).

Ràng buộc

• \(2 \le N \le 1000\).
• Chuỗi có đúng \(N\) ký tự, mỗi ký tự là J, O hoặc I.

Ví dụ

2
OI

7

20
JIOIJOIJOJOIIIOJIOII

4976