问题描述

高桥君正在玩一款经典格斗游戏。

在这个游戏中，需要使用两个按钮 A 和 B。按下按钮 A，高桥君操控的角色将对敌方角色造成伤害。连续按下 $k-1$ 次按钮 A，然后再次按下按钮 A，敌方角色将受到 $k$ 点伤害。按下按钮 B，高桥君操控的角色将摆出一个帅气的姿势。这个操作不会对敌方角色造成任何伤害。

这个游戏非常简单，因此高桥君完全理解了这个游戏的最佳战略。也就是说，只需要连续按下按钮 A 就可以了。然而，这样做很无聊，所以高桥君决定采取一种更重视角色外观的策略。他准备了一个只包含 A 和 B 的字符串 $S$，并重复以下操作 $N$ 次：

• 按下 $|S|$ 次按钮。在第 $i$ 次按下按钮时，如果字符串 $S$ 的第 $i$ 个字符是 A，就按下按钮 A；如果是 B，就按下按钮 B。

请计算完成所有操作后，对敌方角色造成的总伤害值。

约束条件

• $1 ≤ |S| ≤ 10^5$
• $1 ≤ N ≤ 2 × 10^4$
• 字符串 $S$ 仅由字符 A 和 B 组成。

输入

从标准输入读取数据，输入格式如下：

$N$

$S$

输出

输出对敌方角色造成的总伤害值。

示例输入 1

3
ABBAA

示例输出 1

16

高桥君按照顺序按下按钮 ABBAAABBAAABBAA。每次按下按钮 A 时，伤害分别为 $1, 1, 2, 3, 1, 2, 3, 1, 2$。

示例输入 2

4
ABBAAABBAA

示例输出 2

46

示例输入 3

100
AAABAAAABAAAAABBBBBBBBBAABBBBBBAAAAABBB

示例输出 3

4900