{"problem":{"name":"Election","description":{"content":"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 can","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc172_c"},"statements":[{"statement_type":"Markdown","content":"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$.\nNow, the votes will be counted. As each vote is counted, the provisional result will be announced as one of the following three outcomes:\n\n*   **Result A:** Currently, candidate A has more votes.\n*   **Result B:** Currently, candidate B has more votes.\n*   **Result C:** Currently, candidates A and B have the same number of votes.\n\nThere 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.)\nHow many different sequences of provisional results could be announced?\nWhat 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$.\n\n## Constraints\n\n*   $N$ is an integer such that $2 \\leq N \\leq 1000000$.\n*   Each of $c_1, c_2, \\dots, c_N$ is `A` or `B`.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$c_1 c_2 \\cdots c_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc172_c","tags":[],"sample_group":[["4\nAABB","3\n\nIn this sample input, there are four possible orders in which the votes may be counted:\n\n*   The votes are counted in the order of voter $1 \\to 2 \\to 3 \\to 4$.\n*   The votes are counted in the order of voter $2 \\to 1 \\to 3 \\to 4$.\n*   The votes are counted in the order of voter $2 \\to 3 \\to 1 \\to 4$.\n*   The votes are counted in the order of voter $2 \\to 3 \\to 4 \\to 1$.\n\nThe 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."],["4\nAAAA","1\n\nNo matter the order of counting, the sequence of preliminary results will be `AAAA`."],["10\nBBBAAABBAA","5"],["172\nAABAAAAAABBABAABBBBAABBAAABBABBABABABBAAABAAABAABAABBBBABBBABBABBBBBBBBAAABAAABAAABABBBAABAAAABABBABBABBBBBABAABAABBBABABBAAAABAABABBBABAAAABBBBABBBABBBABAABBBAAAABAAABAAAB","24"]],"created_at":"2026-03-03 11:01:14"}}