# Problem G

Ocean's Anti-11 (Hard)

*Note that this is a harder version of the problem
anti11*.

Danny Ocean likes many things: casinos, elaborate heists,
and complicated romantic relationships. But it’s a little-known
fact that Danny loves binary strings most of all — binary
strings of any length and composition. One day, however, he
suddenly develops a mysterious allergy to all binary strings
containing the substring ` 11`. This strange illness lasts exactly one
week, during which time he has to work very hard to avoid any
such “contaminated” binary strings. At the end of the week, the
allergy vanishes as unexpectedly as it appeared, and for a
brief moment Danny is elated that all binary strings are again
available for him to enjoy. Alas, this hope is short lived, for
no sooner has the first allergy disappeared than it is replaced
by anther, this time to all binary strings containing the
substring

`. The second allergy also lasts exactly one week, after which it is replaced by yet another, and another, and so on, one per week, ad infinitum.`

**10101**Danny has (mostly) adjusted to his allergic affliction, and is optimistic that there are still plenty of binary strings for him to enjoy each week, but he’s not sure exactly how many, so he has hired you to write a program to find out.

## Input

The first line of input contains a single integer
$T$ ($1 \leq T \leq 100$) representing the
number of test cases. This is followed by $T$ lines, each of which contains a
single integer $n$
($1 \leq n \leq 10\, 000$)
followed by a non-empty string $b$ consisting only of the characters
` 0` and

`. The length of $b$ is at most $10$.`

**1**## Output

Output consists of $T$ lines, one per case. The output for a given case is the number of binary strings of length $n$ that do not contain $b$ as a substring. Since these values can be quite large, output each value mod $(10^9 + 7)$.

Sample Input 1 | Sample Output 1 |
---|---|

3 1 0 3 101 5 11 |
1 7 13 |