{"problem":{"name":"Shorten ABC","description":{"content":"We have a string $S$ of length $N$ consisting of `A`, `B`, and `C`. You can do the following operation on $S$ zero or more times: *   Choose $i$ $(1 \\leq i \\leq |S| - 1)$ such that $S_i \\neq S_{i + 1","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc110_e"},"statements":[{"statement_type":"Markdown","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)$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^6$\n*   $S$ is a string of length $N$ consisting of `A`, `B`, and `C`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc110_e","tags":[],"sample_group":[["5\nABAAC","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`."],["50\nAACCCCBBBACCCCABABCCCCABACCACACACCACABABBBABABACCB","256972022"]],"created_at":"2026-03-03 11:01:14"}}