Problem M
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 10101. 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.
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 1. The length of $b$ is at most $10$.
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 |
