配点 : 300 点
問題文
高桥君在玩老式的格斗游戏。
在这个游戏中,A 和
将其放在 B 的 2 使用种类的按钮。按钮 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 \times 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