Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Bad Cook

Limits 1s, 512 MB

Mr. Meme has recently moved to a foreign country named “Gloryland” for study purpose. There, he has to cook for himself. But he is not even an amateur. He always messes up his recipe. Say, there are 3 steps in a recipe: Boil, Put Spice, and Fry. He will never do it in order: he may put spice first, then fry, then boil things.

But there is an interesting pattern in his messing up of recipe. Let’s say the recipe includes n steps. He always messes up in such a way that odd-numbered steps never come consecutively in his cooking. So, if the recipe contains 5 steps: 1, 2, 3, 4, 5 - he will never do things like 2, 1, 3, 5, 4 or 2, 1, 4, 3, 5 - where you can find consecutive odd-numbered steps.

And remember, he always messes up!! Doing 1, 2, 3, 4, 5 is not valid in his case although there are no consecutive odd-numbered steps, beacuse it is the right recipe!

Input

The input file will contain T+1 lines (1 <= T <= 2000). First line will contain T, the number of test cases. Each of next T line will contain a single integer N (2<=N<=2000), the number of steps of a recipe.

Output

For each N, print the number of ways Mr. Meme can mess up the recipe. Print the result modulo 1000000007.

Samples

InputOutput
2
4
3
11
1

For the first sample, the valid combinations for N = 4 are: 1243, 1423, 1432 , 2143, 2341, 3214, 3241, 3412, 3421, 4123, 4321. For the second sample, the valid combinations for N = 3 is 321 only.

Discussion