Problem Description

Takahashi is playing an old-school fighting game.

In this game, there are two types of buttons: A and B. Pressing button A causes the character controlled by Takahashi to attack the enemy character. Pressing button A after pressing it $ k-1 $ times in a row causes $ k $ damage to the enemy character. Pressing button B causes the character controlled by Takahashi to strike a cool pose. This action does not inflict any damage to the enemy character.

Since the game is very simple, Takahashi has perfectly understood the optimal strategy for this game. That is, pressing button A continuously is the best strategy. However, this is not interesting, so Takahashi decided to adopt a strategy that emphasizes the appearance of the character. Takahashi prepares a string $ S $ consisting only of A and B, and repeats the following $ N $ times:

• Press the button $ |S| $ times. In the $ i $-th time, press button A if the $ i $-th character of $ S $ is A, and button B if it is B.

After all operations are completed, calculate the total damage inflicted on the enemy character.

Input Format

The input is given from the standard input in the following format:

$ N $ $ S $

Output Format

Output the total damage inflicted on the enemy character.

Sample Input and Output

Sample Input #1

3
ABBAA

Sample Output #1

16

Sample Input #2

4
ABBAAABBAA

Sample Output #2

46

Sample Input #3

100
AAABAAAABAAAAABBBBBBBBBAABBBBBBAAAAABBB

Sample Output #3

4900

Notes/Hints

Constraints

• $1 \leq |S| \leq 10^5$
• $1 \leq N \leq 2 \times 10^4$
• $ S $ consists only of A and B.

Sample Explanation 1

Takahashi presses the buttons in the order of ABBAAABBAAABBAA. When button A is pressed, the damage is added in the order of $ 1, 1, 2, 3, 1, 2, 3, 1, 2 $.

见题面 Input 部分

见题面 Output 部分