{"raw_statement":[{"iden":"problem statement","content":"You are given a string $S$ of length $N$ consisting of characters `A` and `B`.\nYou can perform the following two types of operations zero or more times in any order:\n\n*   Choose a (contiguous) substring `ABA` in $S$ and replace it with `A`.\n*   Choose a (contiguous) substring `BAB` in $S$ and replace it with `B`.\n\nFind, modulo $10^9+7$, the number of possible strings $S$ after performing the operations."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 250000$\n*   $S$ is a string of length $N$ consisting of characters `A` and `B`."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$S$"},{"iden":"sample input 1","content":"4\nABAB"},{"iden":"sample output 1","content":"2\n\nThe two possible strings $S$ after the operations are as follows:\n\n*   `ABAB`: This string can be obtained by performing zero operations.\n*   `AB`: The 1st to 3rd characters of $S=$`ABAB` are `ABA`. Replacing them with `A` results in $S=$`AB`.\n\nHere, the 2nd to 4th characters of $S=$`ABAB` are `BAB`, so you can also replace them with `B`. Note, however, that the resulting `AB` does not count multiple times."},{"iden":"sample input 2","content":"1\nA"},{"iden":"sample output 2","content":"1\n\nNo operations can be performed."},{"iden":"sample input 3","content":"17\nBBABABAABABAAAABA"},{"iden":"sample output 3","content":"18"},{"iden":"sample input 4","content":"100\nABAABAABABBABAABAABAABABBABBABBABBABBABBABBABBABBABBABBABBABBABBABAABABAABABBABBABABBABAABAABAABAABA"},{"iden":"sample output 4","content":"415919090\n\nRemember to take the result modulo $10^9+7$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}