Problem Background

Note: This problem includes a large sample case.

Note: The nine-linked rings in this problem are different from traditional nine-linked rings.

The nine-linked rings are a traditional Chinese puzzle game. As shown in the figure, nine circular rings are placed on a "sword" and interconnected.

In traditional nine-linked rings, the $k$-th ring ($k \ge 2$) can be placed on the "sword" (denoted as $1$) or removed from the "sword" (denoted as $0$) if and only if the $(k-1)$-th ring is on the sword and all previous rings are not on the sword. Specifically, the first ring can be placed or removed at will.

In this problem, we will discuss a more general case, although this simple nine-linked ring may not necessarily be physically constructible.

Problem Description

A simple nine-linked ring can be seen as two 01 strings—the rule string $s$ and the state string $t$, satisfying $|s| = |t| - 1$. Here, $t_i = \texttt{1}$ indicates that the $i$-th ring is placed, and $t_i = \texttt{0}$ indicates that the $i$-th ring is removed.

$s$ remains unchanged during the game, while $t$ changes the value at one position (from 0 to 1 or from 1 to 0) in each step. A simple nine-linked ring is considered removed if and only if all $t_i$ are 0; it is considered placed if and only if all $t_i$ are 1.

The simple nine-linked ring stipulates that $t_i$ can 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 are a special case where $s$ is 00...01.

Given an $s$, determine the minimum number of steps required to transition from the removed state to the placed state, modulo $10^9+7$.

Input Format

The first line contains an integer $n$, representing the length of $s$. Note that this is not the number of rings.

The second line contains a 01 string $s$.

Output Format

A single line containing an integer, representing the answer modulo $10^9+7$.

Sample Input and Output

Sample Input #1

3
011

Sample Output #1

6

Sample Input #2

8
00000001

Sample Output #2

341

Sample Input #3

See attached file samples/rings3.in

Sample Output #3

See attached file samples/rings3.ans

Sample Input #4

See attached file samples/rings4.in

Sample Output #4

See attached file samples/rings4.ans

Notes

Sample 1 Explanation

Initially, all rings are not on the simple nine-linked ring, and the state string $t$ is 0000.

Step 1: Place the first ring, $t$ becomes 1000.

Step 2: Place the second ring, $t$ becomes 1100.

Step 3: Place the third ring, $t$ becomes 1110.

You cannot directly place the fourth ring next because 111 is not a suffix of the rule string $s` `011`. Therefore, step 4 should remove the first ring, $t$ becomes 0110.

Then step 5 places the fourth ring, $t$ becomes 0111.

Finally, step 6 places the first ring, $t$ becomes 1111, achieving the goal.

Sample 2 Explanation

This is the traditional nine-linked ring with exactly 9 rings.

Sample 3 Explanation

Sample 3 meets the constraints of test point 7.

Sample 4 Explanation

Sample 4 meets the constraints of test point 15.

Data Size and Constraints

For $100\%$ of the data, $1 \le n \le 2000$, $s_i \in \{\texttt{0}, \texttt{1}\}$.

见题面 Input 部分

见题面 Output 部分