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, 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

InputOutput
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.


Discussion

Statistics


73% Solution Ratio

atiqurrahman99Earliest, 5M ago

prodip_bsmrstuFastest, 0.0s

random_shuffleLightest, 131 kB

sarthakmannaShortest, 342B

Submit

Login to submit

Related Contests