A sequence of integers from ~1~ to ~N~ is said to be zig zag if the sequence contains each integer exactly once and, indexing from one, every element at an even index is greater than the preceding one, and every element at an odd index is less than the preceding one.

For example:

Sequence
~1, 3, 2, 5, 4~	is zig zag
~2, 5, 3, 4, 1~	is zig zag
~1, 5, 4, 2, 3~	is NOT zig zag (the fourth element is less than the third element)

Input Specification

The input will contain ~10~ test cases. Each test case has one line with the integer ~N~ ~(1 \le N \le 10\,000)~.

For the first four test cases in the file, ~N \le 10~. For the first seven cases, ~N \le 200~.

Output Specification

For each test case, output the number of unique zig zag sequences possible for that value of ~N~, modulo ~1\,000\,000\,007~ or ~10^9+7~.

"Modulo ~1\,000\,000\,007~" means that if the answer is ~123\,456\,789\,123~ you should output ~456\,788\,262~ because that's the remainder of ~123\,456\,789\,123~ divided by ~1\,000\,000\,007~.

Sample Input

3
4
5

Sample Output

2
5
16

Note: Only ~3~ cases are shown in this sample.

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org