该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

航空

题目描述

新一在瑞士「苏黎世联邦理工学院」研学，小兰准备飞往瑞士和新一见面。在机场，小兰听到一段播放，"需要搭乘中国南方航空、中国东方航空、海南航空、厦门航空、上海航空、山东航空、四川航空、深圳航空、青岛航空、昆明航空、新加坡航空、俄罗斯航空、肯尼亚航空、日本航空的乘客请往 11 号候厅走……"

小兰觉得这段播报非常有趣，于是将它记录了下来，发给了新一。然而，由于机场过于拥挤，小兰的网络收到了神秘力量的干扰，使新一收到的是一个大小写字母的字符串 $S$。

现在，新一想把 $S$ 分割 成至少两个航空公司的名字（不能有剩余的不属于任何一个航空公司的名字的部分），分割成的航空公司的名字可以重复。他想知道方案数模 P 的结果。

一个大小写字母的字符串被称为一个 「航空公司的名字」，当切仅当字符串「Air」是它的后缀。

• 例如「Air」「CTAir」「AirAir」都是航空公司的名字，而「clearair」「Airplane」都不是。

输入格式

第一行一个整数 $P$。

第二行一个大小写拉丁字母的字符串 $S$。

输出格式

一行一个整数表示答案。

样例 #1

样例输入 #1

9
AirplaneLovesCleanAir

样例输出 #1

1

样例 #2

样例输入 #2

764806970
AirAirAirAirAirpojHDUzIuUhAir

样例输出 #2

31

提示

对于前 $20\%$ 的数据，$|S|\le 10$；

对于前 $40\%$ 的数据，$|S|\le 100$；

对于前 $60\%$ 的数据，$|S|\le 1000$；

对于 $100\%$ 的数据，$3 \le |S|\le 10^6,9 \le P \le 10^9+7$。