{"problem":{"name":"ABA and BAB","description":{"content":"You are given a string $S$ of length $N$ consisting of characters `A` and `B`. You can perform the following two types of operations zero or more times in any order: *   Choose a (contiguous) substri","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc180_a"},"statements":[{"statement_type":"Markdown","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.\n\n## Constraints\n\n*   $1 \\leq N \\leq 250000$\n*   $S$ is a string of length $N$ consisting of characters `A` and `B`.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$S$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc180_a","tags":[],"sample_group":[["4\nABAB","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."],["1\nA","1\n\nNo operations can be performed."],["17\nBBABABAABABAAAABA","18"],["100\nABAABAABABBABAABAABAABABBABBABBABBABBABBABBABBABBABBABBABBABBABBABAABABAABABBABBABABBABAABAABAABAABA","415919090\n\nRemember to take the result modulo $10^9+7$."]],"created_at":"2026-03-03 11:01:14"}}