Background

AK-47 自动步枪于 1947 年定型，1949 年装备苏联部队。除了大规模装备于苏军外，世界 上有许多国家也都进行了仿制或授权生产 AK 步枪系列，其中包括德国、捷克斯洛伐克、 前南斯拉夫、匈牙利、中国、波兰、罗马尼亚、保加利亚、埃及、古巴、朝鲜等多个国 家。AK-47 的设计思路也影响了以色列、芬兰、中国等多个国家的步枪设计构思路线。按 不同统计 AK 系列包括了未经许可生产的仿制品，总产量超过 1 亿支，是世界上产量最 高、适用范围最广和改进类型最多的枪械。

Description

现在 Bob 有一个字符串。字符串中有许多数字和大小写字母。Bob 的任务是从中计数有几 个不同的子序列，可以形成 AK47 这样一个字符串。

Format

Input

第一行一个正整数 $n$，表示接下来给定的字符串长度。 接下来一行一个字符串，字符串中包括大小写字母和数字。

Output

计数字符串中的 AK47 子序列的数量并输出。

Samples

8
AAKK4477

16

样例 1 解释

上面这个例子中任意选一个 A 一个 K 一个 4 一个 7 即可。总方案有 16 种。

12
AAK4QQK477dd

12

样例 2 解释

选第一个 K 的方法有 2*2*2=8 种，选第二个 K 的方法有 2*2=4 种，共计 12 种。

大数据样例

下载 in out

数据范围

#1～#3, 1<=len<=10
#4~#5, 1 ≤ 𝑙𝑒𝑛 ≤ 1000 字符串形如𝐴 … 𝐴𝐾 … 𝐾4 … 47 … 7
#6~#7, 1 ≤ 𝑙𝑒𝑛 ≤ 1000
#8~#10, 2 ≤ 𝑙𝑒𝑛 ≤ 100,000

Limitation

1s, 1024KiB for each test case.