AT_arc172_c [ARC172C] Election

在今年的 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$

请输出答案。

## 限制条件 - $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 翻译