Problem X
Ocean's Anti-11
Note that this is an easier version of the problem
anti11hard.
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. Recently, however, he has developed an unfortunate allergy to binary strings containing the substring 11. He is optimistic that there are still plenty of other binary strings for him to enjoy, 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$).
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 11 as a substring. Since these values can be quite large, output each value mod $(10^9 + 7)$.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 10 |
3 144 |
