GUMATH2 - Card Meets (medium)

no tags 

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 11-02-2017, after compiler changes : 0.00s with C, 0.22s with PY3.5. New TL.


hide comments
hodobox: 2017-07-14 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: 2016-12-07 22:53:38

@Francky
How can i optimize my code??

=(Francky)=> You could use some precomputation to speedup seriously. Moreover your mod-mul method is a bit slow using ll al the time.
@Francky-Can you suggest me any other combinatorics problem which you wrote or is good. You have written so many problems..I can't check them all.

Last edit: 2017-01-16 15:26:05
iloveaakanksha: 2016-06-23 19:33:06

@Francky is My logic correct or am I far from it?
Submission ID : 17165527

=(Francky)=> You have AC one the first input file (small cases), but WA on other ones (some but not all high values). You have to find what is the bug in your code... Good luck. It main need another method...

Last edit: 2016-06-23 20:20:55
aishik_pyne: 2015-09-02 19:14:45

what do you mean by modulo 10000009 ?

=(Francky)=> https://en.wikipedia.org/wiki/Modulo_operation

Last edit: 2015-09-02 21:53:39
Francky: 2015-01-19 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: 2015-01-18 14:41:27

please provide some test cases in the range 10^12 to 10^18
--(Francky)--> No other test cases are provided.

Last edit: 2015-01-18 14:45:45
knb_dtu: 2014-05-16 07:26:27

@Francky:-Why does my program gives NZEC error?(Submission ID:11588126)
--ans(Francky)--> Try small cases. Good luck.

Last edit: 2014-05-16 07:37:18
Apoorv Jindal: 2014-01-09 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.
--ans(Francky)--> It is a correct answer, you can boost with computation tricks.
EDIT -> Your C code ran in 0.08s (Congrats, you are an awesome programmer).What kind of computation tricks, I cant think of any,that will make such a difference in the running time.

Last edit: 2014-01-10 02:22:43

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