What is the Problem?
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:
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 Specifications
DATA41.txt (DATA42.txt for the second try) will contain 10 test cases. Each test case has one line with the integer N (1 ≤ N ≤ 10,000). For the first four test cases in the file, N ≤ 10. For the first seven cases, N ≤ 200.
Output Specifications
For each test case, output the number of unique zig zag sequences possible for that value of N, modulo 1,000,000,007. “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 cases shown)
3
4
5
Sample Output
2
5
16