# 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

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

Input | Output |
---|---|

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.

Login to submit