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:

5