{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $T$ is a string of length $N$ consisting of `0` and `1`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$N$\n$T$"},{"iden":"sample input 1","content":"4\n1011"},{"iden":"sample output 1","content":"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$"},{"iden":"sample input 2","content":"22\n1011011011011011011011"},{"iden":"sample output 2","content":"9999999993"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}