Hide

Problem C
Ocean's Anti-11

/problems/anti11/file/statement/en/img-0001.png
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.

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

Please log in to submit a solution to this problem

Log in