题目描述

在今年的睿爸校长选举中，有两位候选人 A 和 B 参选，共有 $N$ 名老师和学生进行了投票。每位投票者都被编号为 $1$ 到 $N$，第 $i$ 位投票者（$1 \leq i \leq N$）投给了 $c_i$ 候选人。

现在即将进行计票。计票过程中，每次会开出一张选票，并在每次开票后，公布当前的计票结果，结果分为以下三种情况之一：

• 结果 A： 目前为止，A 候选人的得票数更多。
• 结果 B： 目前为止，B 候选人的得票数更多。
• 结果 C： 目前为止，A 和 B 的得票数相同。

计票顺序有如下规则：除了投票者徐老师的编号为 $1$ 的选票外，其他选票必须按照投票者编号从小到大的顺序依次开票（即 $2,3,\dots,N$ 依次开票）。徐老师作为现任校长，他的选票可以在任意时刻开票。

请你计算，所有可能的计票结果序列有多少种。

计票结果序列是指每张票开出时公布的结果 $s_i$（A、B 或 C 之一），即字符串 $s_1 s_2 \dots s_N$。

输入格式

第一行一个正整数 $N（2 \leq N \leq 1000000 ）$，表示该校的投票人数。

第二行一个长度为 $N$ 的仅包含 AB 的字符串，按照编号顺序给出该校所有人的投票情况。

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4
AABB

输出 #1

3

输入输出样例 #2

输入 #2

4
AAAA

输出 #2

1

输入输出样例 #3

输入 #3

10
BBBAAABBAA

输出 #3

5

输入输出样例 #4

输入 #4

172
AABAAAAAABBABAABBBBAABBAAABBABBABABABBAAABAAABAABAABBBBABBBABBABBBBBBBBAAABAAABAAABABBBAABAAAABABBABBABBBBBABAABAABBBABABBAAAABAABABBBABAAAABBBBABBBABBBABAABBBAAAABAAABAAAB

输出 #4

24

样例解释 1

在这个输入样例中，计票顺序可能有以下 $4$ 种：

• 按 $1 \to 2 \to 3 \to 4$ 的顺序计票。
• 按 $2 \to 1 \to 3 \to 4$ 的顺序计票。
• 按 $2 \to 3 \to 1 \to 4$ 的顺序计票。
• 按 $2 \to 3 \to 4 \to 1$ 的顺序计票。

计票结果序列分别为 AAAC、AAAC、ACAC、ACBC，因此可能的计票结果序列有 $3$ 种。

样例解释 2

无论以何种顺序计票，计票结果序列始终为 AAAA。