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, because it is the right recipe!
Input
The first line will contain T (1 ≤ T ≤ 2000), the number of test cases. Each of the next T lines 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.
Sample
| Input | Output |
|---|---|
2 4 3 | 11 1 |
For the first input, the valid combinations for N = 4 are: 1243, 1423, 1432, 2143, 2341, 3214, 3241, 3412, 3421, 4123, and 4321. For the second input, the valid combinations for N = 3 is 321 only. | |
