MINI  MINI IN DANGER!!!
There is a n x n board.
Tom is playing a game in which there are n*n blocks which can be filled with numbers from 0 to n1 in some arbitrary way.
The rule of the game is that the board should be filled in such a way that the sum of each row and column should be divisible by n.
Tom has set the board in the winning configuration.But now the intelligent and notorious daughter of Tom, Mini comes and changes the configuration of the board.
But she is scared now as her dad is about to come home.She realizes that dad will get angry if he sees that the board is not in the winning configuration and
he will scold her.Mini wants to know the number of ways in which the board can be restored to a winning configuration.Please help her out.
INPUT
First line consits of an integer T and then T test cases follow.
Having the value of N
OUTPUT
For each test case you have to output the ways%1000000009 in a seperate line.
Constraints:
T <= 10^6
N will be between 1 and 2^641 and not a multiple of 1000000009
SAMPLE EXAMPLE
Input:
1
1
Output:
1
hide comments
rainy jain :
20160511 05:56:16
Last edit: 20160511 05:59:19 

[Lakshman]:
20140614 13:50:21
What is the answer for 3? Can some One give me a test case. 
Added by:  anuj 
Date:  20120205 
Time limit:  0.216s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  own 