{"raw_statement":[{"iden":"problem statement","content":"We have a string $S$ of length $N$ consisting of `A`, `B`, and `C`.\nYou can do the following operation on $S$ zero or more times:\n\n*   Choose $i$ $(1 \\leq i \\leq |S| - 1)$ such that $S_i \\neq S_{i + 1}$. Replace $S_i$ with the character (among `A`, `B`, and `C`) that is different from both $S_i$ and $S_{i + 1}$, and remove $S_{i + 1}$ from $S$.\n\nFind the number of distinct strings that $S$ can be after zero or more operations, and print the count modulo $(10^9+7)$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 10^6$\n*   $S$ is a string of length $N$ consisting of `A`, `B`, and `C`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$S$"},{"iden":"sample input 1","content":"5\nABAAC"},{"iden":"sample output 1","content":"11\n\nFor example, the following sequence of operations turns $S$ into `ACB`:\n\n*   First, choose $i=2$. We replace $S_2$ with `C` and remove $S_3$, turning $S$ into `ACAC`.\n*   Then, choose $i=3$. We replace $S_3$ with `B` and remove $S_4$, turning $S$ into `ACB`."},{"iden":"sample input 2","content":"50\nAACCCCBBBACCCCABABCCCCABACCACACACCACABABBBABABACCB"},{"iden":"sample output 2","content":"256972022"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}