问题陈述

今年的ATCoder市长选举有A和B两名候选人， $N$ 名选民投了票。

投票人被分配了从 $1$ 到 $N$ 的编号，投票人 $i$ $(1 \leq i \leq N)$ 为候选人 $c_i$ 投票。

现在，选票将被计算。

每次计票时，临时结果将作为以下三种结果之一公布：

-**结果A：**目前，候选人A得票较多。-**结果B：**目前，候选人B拥有更多票数。

-**结果C：**目前，候选人A和B的票数相同。

有一条关于计票顺序的规则：除投票人 $1$ 以外的所有投票人的投票必须按其投票人编号的升序进行计算

贝尔斯。(投票人 $1$ 的投票可随时计算。)

可以宣布多少种不同的临时结果？

临时结果的顺序是什么？设 $s_i$ 为计算第 $i$ 次投票 $(1 \leq i \leq N)$ 时报告的结果( A 、 B 或 C )。

临时结果的序列引用字符串 $s_1 s_2 \dots s_N$ 。

以上为机器翻译结果，仅供参考。

Problem Statement

This year's AtCoder mayoral election has two candidates, A and B, and $N$ voters have cast their votes. The voters are assigned numbers from $1$ to $N$, and voter $i$ $(1 \leq i \leq N)$ voted for candidate $c_i$.

Now, the votes will be counted. As each vote is counted, the provisional result will be announced as one of the following three outcomes:

• Result A: Currently, candidate A has more votes.
• Result B: Currently, candidate B has more votes.
• Result C: Currently, candidates A and B have the same number of votes.

There is a rule regarding the order of vote counting: votes from all voters except voter $1$ must be counted in ascending order of their voter numbers. (The vote from voter $1$ may be counted at any time.)

How many different sequences of provisional results could be announced?

What is a sequence of provisional results?Let $s_i$ be the result (A, B, or C) reported when the $i$-th vote $(1 \leq i \leq N)$ is counted. The sequence of provisional results refers to the string $s_1 s_2 \dots s_N$.

Constraints

• $N$ is an integer such that $2 \leq N \leq 1000000$.
• Each of $c_1, c_2, \dots, c_N$ is A or B.

Input

The input is given from Standard Input in the following format:

$N$

$c_1 c_2 \cdots c_N$

Output

Print the answer.

Sample Input 1

4
AABB

Sample Output 1

3

In this sample input, there are four possible orders in which the votes may be counted:

• The votes are counted in the order of voter $1 \to 2 \to 3 \to 4$.
• The votes are counted in the order of voter $2 \to 1 \to 3 \to 4$.
• The votes are counted in the order of voter $2 \to 3 \to 1 \to 4$.
• The votes are counted in the order of voter $2 \to 3 \to 4 \to 1$.

The sequences of preliminary results for these will be AAAC, AAAC, ACAC, ACBC from top to bottom, so there are three possible sequences of preliminary results.

Sample Input 2

4
AAAA

Sample Output 2

1

No matter the order of counting, the sequence of preliminary results will be AAAA.

Sample Input 3

10
BBBAAABBAA

Sample Output 3

5

Sample Input 4

172
AABAAAAAABBABAABBBBAABBAAABBABBABABABBAAABAAABAABAABBBBABBBABBABBBBBBBBAAABAAABAAABABBBAABAAAABABBABBABBBBBABAABAABBBABABBAAAABAABABBBABAAAABBBBABBBABBBABAABBBAAAABAAABAAAB

Sample Output 4

24

What is a sequence of provisional results?Let $s_i$ be the result (A, B, or C) reported when the $i$-th vote $(1 \leq i \leq N)$ is counted. The sequence of provisional results refers to the string $s_1 s_2 \dots s_N$.