問題文

高橋君は、古き良き格闘ゲームで遊んでいます。

このゲームでは、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