P9229 Simple Nine Linked Rings

**Hint: This problem has a large sample.** **Hint: The “nine linked rings” in this problem are different from the traditional nine linked rings.** Nine linked rings are a traditional Chinese puzzle game. As shown in the figure, nine rings are placed on a “sword” and are linked with each other.  In the traditional nine linked rings, the $k(k\ge 2)$-th ring can be put onto the “sword” (denoted as $1$) or taken off the “sword” (denoted as $0$) if and only if the $(k-1)$-th ring is on the sword, and all rings before it are not on the sword. In particular, the $1$-st ring can be put on or taken off freely. In this problem, we discuss a more general situation, although this simple nine linked rings may not necessarily be physically constructible.

A simple nine linked rings can be viewed as two `01` strings: the rule string $s$ and the state string $t$, satisfying $|s|=|t|-1$. Here, $t_i=\texttt 1$ means the $i$-th ring is on, and $t_i=\texttt 0$ means the $i$-th ring is off. Within the same game, $s$ never changes, while in each step $t$ changes the value at exactly one position (from `0` to `1` or from `1` to `0`). The simple nine linked rings is fully taken off if and only if all $t_i$ are `0`. The simple nine linked rings is fully put on if and only if all $t_i$ are `1`. The rule of the simple nine linked rings is: $t_i$ is allowed to change if and only if $t_{1\sim i-1}$ is a **suffix** of $s$. It can be seen that the traditional nine linked rings is a special case where $s$ is `00...01`. Given $s$, find the minimum number of steps needed to go from the fully taken-off state to the fully put-on state. Output the answer modulo $10^9+7$.

The first line contains an integer $n$, the length of $s$. **Note that this is not the number of rings.** The second line contains a `01` string $s$.

One line containing an integer, the answer modulo $10^9+7$.

### Explanation for Sample 1 At the initial moment, all rings are not on the sword, and the state string $t$ is `0000`. In step 1, put on the $1$-st ring, and $t$ becomes `1000`. In step 2, put on the $2$-nd ring, and $t$ becomes `1100`. In step 3, put on the $3$-rd ring, and $t$ becomes `1110`. Next, you cannot directly put on the $4$-th ring, because `111` is not a suffix of the rule string $s$ `011`. Therefore, in step 4 you should take off the $1$-st ring, and $t$ becomes `0110`. Then in step 5, put on the $4$-th ring, and $t$ becomes `0111`. In the last step, put on the $1$-st ring, and $t$ becomes `1111`, completing the goal. ### Explanation for Sample 2 This is the traditional nine linked rings, and there are exactly $9$ rings. ### Explanation for Sample 3 Sample 3 satisfies the constraints of test point $7$. ### Explanation for Sample 4 Sample 4 satisfies the constraints of test point $15$. ### Constraints For $100\%$ of the testdata, $1\le n\le 2000$, $s_i\in\{\texttt 0,\texttt 1\}$. |Test point ID|$\vert s\vert\le$|Special property| |:-:|:-:|:-:| |$1\sim 3$|$3$|| |$4\sim 6$|$15$|| |$7\sim 11$|$300$|| |$12\sim 13$|$1000$|| |$14$|$2000$|All $s_i$ are `0`.| |$15\sim 17$|$2000$|The last character of $s$ is `1`, and all other positions are `0`.| |$18\sim 25$|$2000$|| Translated by ChatGPT 5