Ocean's Anti-11

Image by Liam Keliher and KeepCalmStudio.com

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

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