Problem Statement:
Mark loves math so mush especially counting problems that has the famous phrase "In how many ways we can ?.", so he can't live a day without solving a counting problem.
Today, while he was searching for a new problem to solve, he found one that looked really hard.
The problem defines a string called "Bit string", a string of only ones and zeroes, and asks: In how many ways we could form a bit string of length n that has no two consecutive zeroes.
For example: the bit strings of length n = 3 are :
000 , 100 , 010 , 001 , 110 , 101 , 011 , 111
we notice that we have five bit strings of length n = 3 that have no two consecutive zeroes.
Mark needs your help to solve this hard problem!

Input Format:
The first line has 1 <= T <= 1000, the number of test cases.
The next T lines, each one has 1 <= n <= 1000, the length of the bit string.

Output Format:
For each test case print the number of bit strings of length n that have no two consecutive zeroes.
The result maybe too large so print the result mod 10^9 + 7.

Sample Input:
1 3

Sample Output:

Added by: muaz.32
Added at: 2015-03-13 13:00:00 UTC
Time Limit: 3 seconds
Partial score: No
Source:DCPC training 2015