{"raw_statement":[{"iden":"problem statement","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$."},{"iden":"constraints","content":"*   $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`."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$c_1 c_2 \\cdots c_N$"},{"iden":"sample input 1","content":"4\nAABB"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"4\nAAAA"},{"iden":"sample output 2","content":"1\n\nNo matter the order of counting, the sequence of preliminary results will be `AAAA`."},{"iden":"sample input 3","content":"10\nBBBAAABBAA"},{"iden":"sample output 3","content":"5"},{"iden":"sample input 4","content":"172\nAABAAAAAABBABAABBBBAABBAAABBABBABABABBAAABAAABAABAABBBBABBBABBABBBBBBBBAAABAAABAAABABBBAABAAAABABBABBABBBBBABAABAABBBABABBAAAABAABABBBABAAAABBBBABBBABBBABAABBBAAAABAAABAAAB"},{"iden":"sample output 4","content":"24"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}