ECOO '17 R2 P4 - Zig Zag

View as PDF

Submit solution

Points: 12 (partial)
Time limit: 13.0s
Memory limit: 256M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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


Sample Output


Note: Only 3 cases are shown in this sample.

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


There are no comments at the moment.