問題文

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

このゲームでは、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 のみからなる。

入力例 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