JZPCIR - Jumping Zippy
Jumping Zippy likes to jump. He jumps every day and feels boring. Then he think of a new way to jump. He jumps on a big round plaza. The plaza is divided into n sectors numbered clockwise from 0 to n-1. Firstly, he stands on sector 0. Each time, when he is stand on sector x, he can jump to sector (x-2)%n, (x-1)%n, (x+1)%n or (x+2)%n. His goal is to jump to each sector exactly once and jump back to sector 0 at last. And for the first jump, he never jumps to sector n-1 or sector n-2. He wants to find the number of different ways in which he can complete his goal.
First line is a number t, which is the number of testcases. (1<=t<=1000)
Then following t lines, each line contains a integer n, which is the number of sectors. (5<=n<=10^18)
For each query n, output a line which contains one integer, the number of different ways Zippy can complete his goal in, modulo 10^9+9.
Input: 5 5 6 7 8 9 Output: 12 16 23 29 41