GUMATH2  Card Meets (medium)
Guardian is very weak at maths but still to compete in a certain exam he has to get good grades in mathematics this time. In the first class of the semester the Prof. asked students to find the number of ways deck (having N cards) could be shuffled that exactly one card is at the same position as before, and the students who successfully do this will be awarded with good marks in mid terms. Help Guardian solve this problem.
Input
The input begins with the number T of test cases in a single line.
In each of the next T lines there are one integer N.
Output
For each test case you have to output on a single line the number of ways possible meeting the Prof.'s requirements.
As the answer can be a huge number, simply output it modulo 10000009.
Example
Input: 1 3 Output: 3
Let's say the initial deck configuration was {1,2,3}, then three possible shuffles are {1,3,2}, {2,1,3}, {3,2,1}.
Constraints
1 < T < 10^4 0 < N < 10^18
@speed addicts : my C code ran in 0.08s, and my python3 code ran in 3.2s. (Total time with Pyramid cluster)
Edit 19/I/2015 : Now the problem use Cube cluster, rejudge of my old code gave 0.01s with C, and 0.57s with Py3.2 (this last one ends in 0.42s with PY3.4)
Edit 11022017, after compiler changes : 0.00s with C, 0.22s with PY3.5. New TL.
hide comments
hodobox:
20170714 07:34:43
Bah, my default solution ran in like 0.33s, but I couldn't strip it down any further. Well, finally a problem which forced me to apply CRT :P 

rrm_2016:
20161207 22:53:38
@Francky


iloveaakanksha:
20160623 19:33:06
@Francky is My logic correct or am I far from it?


aishik_pyne:
20150902 19:14:45
what do you mean by modulo 10000009 ?


Francky:
20150119 14:43:20
Description updated as this problem is now using cube cluster. Let us know, for that problem or another, if something strange happened with the cluster switch. 

ADITYA PRAKASH:
20150118 14:41:27
please provide some test cases in the range 10^12 to 10^18


knb_dtu:
20140516 07:26:27
@Francky:Why does my program gives NZEC error?(Submission ID:11588126)


Apoorv Jindal:
20140109 13:19:54
@Francky Is my algorithm the expected solution? Or is there something better? Curious as to what the expected algorithm is.Ingenious problem btw.

Added by:  Francky 
Date:  20130126 
Time limit:  0.300s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  GUMATH 