Background

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.

Problem Description

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$.

Input Format

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$.

Output Format

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

3
011

6

8
00000001

341

见附件中的 samples/rings3.in

见附件中的 samples/rings3.ans

见附件中的 samples/rings4.in

见附件中的 samples/rings4.ans

Hint

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\}$.

Translated by ChatGPT 5