{"problem":{"name":"Many 110","description":{"content":"Let $S$ be the concatenation of $10^{10}$ copies of the string `110`. (For reference, the concatenation of $3$ copies of `110` is `110110110`.) We have a string $T$ of length $N$. Find the number of t","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_b"},"statements":[{"statement_type":"Markdown","content":"Let $S$ be the concatenation of $10^{10}$ copies of the string `110`. (For reference, the concatenation of $3$ copies of `110` is `110110110`.)\nWe have a string $T$ of length $N$.\nFind the number of times $T$ occurs in $S$ as a contiguous substring.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $T$ is a string of length $N$ consisting of `0` and `1`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$T$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc110_b","tags":[],"sample_group":[["4\n1011","9999999999\n\n$S$ is so long, so let us instead count the number of times `1011` occurs in the concatenation of $3$ copies of `110`, that is, `110110110`. We can see it occurs twice:\n\n*   $1$ `1011` $0110$\n    \n*   $1101$ `1011` $0$"],["22\n1011011011011011011011","9999999993"]],"created_at":"2026-03-03 11:01:14"}}