A - ファイティング・タカハシ

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300

問題文

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

このゲームでは、AB2 種類のボタンを使います。ボタン A を押すと、 高橋君の操作するキャラクターは敵キャラクターに攻撃を加えます。k-1 回連続でボタン A を押した後にボタン A を押したとき、 敵キャラクターには k のダメージが加わります。 ボタン B を押すと、高橋君の操作するキャラクターは格好いいポーズを取ります。この操作では、敵キャラクターにはダメージは加わりません。

このゲームは非常に単純なので、高橋君はこのゲームの最適戦略を完璧に理解してしまいました。 すなわち、ボタン A だけを押し続けるのが最も良い、ということです。 しかしこれでは面白くないので、高橋君はキャラクターの見た目を重視した、次のような戦略をとることにしました。 高橋君は AB のみからなる文字列 S を用意し、以下を N 回繰り返します。

  • |S| 回ボタンを押す。i 回目には、Si 文字目が A ならボタン A を、B ならボタン B を押す。

すべての操作を終えた後に、敵キャラクターに加わったダメージの合計値を求めてください。

制約

  • 1 ≦ |S| ≦ 10^5
  • 1 ≦ N ≦ 2 \times 10^4
  • SAB のみからなる。

入力

入力は以下の形式で標準入力から与えられる。

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