← 返回题目列表

AtCoder · joi2014yo_d

D. 俱乐部活动日程(Schedule)

中文机器翻译题面 查看原题

配点: 100 点

問題

IOI高中的编程社中,有J君、O君和I君三名成员。 3 编程社试图安排社团的日程。

今,N 他们正在决定白天活动的日程。作为各活动日的日程,对于每名成员来说是否参加活动有两种可能性, 2 作为整个社团,总共有 8 种可能。社团室的钥匙只有 1 只有一个,最初由 J 君持有。每次活动日,参加当天活动的部员中必须有一个人持有钥匙, 1 活动结束后,参加的部员中有一个人会把钥匙带回去。

在编程社,为了确保每次活动日都能进行活动,事先确定了每个活动日的负责人。负责人必须出席当天的活动。

给出了想要确定计划的天数,以及每个活动当天的负责人是谁的信息,编写一个程序,求作为可以在所有活动日进行社团活动的计划表可能的数量对 10\,007 取余的结果。不过,社团活动结束时带钥匙回家的成员,可以是当天参加活动的任何成员,并且最后一天谁带钥匙回家都可以。


入力

输入是,2 行组成。

1 行表示计划日数 1 整数 N (2 \leqq N \leqq 1000) 已书写。

2 行表示各活动日的负责人 N 写有由字符组成的字符串。这个字符串的 i 文字目 (1 \leqq i \leqq N) 表示i 第几天活动的负责人。也就是说,i 第一个字母是 J,O,I 分别意味着 i 第几天活动的负责人是J君、O君、I君。

出力

作为计划表可以考虑的数量 10\,007 后的余数 输出为 1 行。 在


入力例 1

2
OI

出力例 1

7

入出力例 1 中, 2 考虑每天活动的时间表。1 当天的负责人是O先生。 2 当天负责人是I先生,符合问题陈述条件的日程表是 7 有几种可能性。

此表中,J、O、I分别代表J先生、O先生、I先生当天的参与情况。1 当天的负责人是O先生,但最初拥有钥匙的人是J先生,所以1 请注意,J和O均需参加当天的活动。另外,1 当天带着钥匙回来的人 2 当天我也必须参加,所以1 日和 2 两天至少有一人参加 1 注意,必须有一个人。


入力例 2

20
JIOIJOIJOJOIIIOJIOII

出力例 2

4976

入出力例 2 中,满足条件的所有明细表 72\,493\,594\,992 有几种可能性。那个 输出 10\,007 所得的余数 4\,976 。