题目描述

在今年的 AtCoder 市长选举中，有两位候选人 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$ 依次开票）。投票者 $1$ 的选票可以在任意时刻开票。

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

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

输入格式

输入通过标准输入给出，格式如下：

$N$ $c_1\ c_2\ \cdots\ c_N$

输出格式

请输出答案。

样例 1

输入

4
AABB

输出

3

样例 2

输入

4
AAAA

输出

1

样例 3

输入

10
BBBAAABBAA

输出

5

样例 4

输入

172
AABAAAAAABBABAABBBBAABBAAABBABBABABABBAAABAAABAABAABBBBABBBABBABBBBBBBBAAABAAABAAABABBBAABAAAABABBABBABBBBBABAABAABBBABABBAAAABAABABBBABAAAABBBBABBBABBBABAABBBAAAABAAABAAAB

输出

24

说明/提示

限制条件

• $N$ 是满足 $2 \leq N \leq 1000000$ 的整数。
• $c_1, c_2, \dots, c_N$ 均为 A 或 B。

样例解释 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。

由 ChatGPT 4.1 翻译