SPOJ.com - Problem GUMATH

GUMATH - Guardian and The Deck of Cards

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

First line contains an integer T, the number of test cases (T <= 10000). Then following T lines contain an integer N (N <= 1000000) the number of cards in the deck.

Output

For each test case you have to output the number of ways possible meeting the Prof's requirements modulo 10000009.

Example

Input:
1
3

Output:
3

Let's say the initial deck configuration was {1, 2, 3}, then 3 possible shufflings are {1, 3, 2}, {2, 1, 3}, {3, 2, 1}

Submit solution!

hide comments



	Francky: 2013-01-28 10:32:21 @ D : Good decision. What about a thread in the forum to discuss of various problems ? I have some suggestions.
	:D: 2013-01-28 09:08:21 this: Moved to tutorial. VIDEO: You are right. It's strange, since I got a non 0.00 time and I seem not to have any precomputation. Maybe something "got broken" along the way. I'll try to contact the problem author. TIGA: left in tutorial and DIVSUM also moved there. I know there is a lot of mess concerning classical / tutorial classification. For now I focus on younger problems that would give a lot of points. If problem has 1000+ AC's it's already of marginal value. There is a chance that we will have scoring for tutorial (for example 0.25 of classical). Then I will probably make a bigger cleanup. If you find any more issues please send the an e-mail (see my account page). We can also discuss SPOJ issues there, if you want. It's just easy to miss comments. Last edit: 2013-01-28 09:10:31
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-01-26 18:08:04 @Zukow: Could you hide "VIDEO" problem? and move "TIGA" problem back to classical? I've leave comments to that both problems for the reason.. Last edit: 2013-01-26 18:08:38
	Francky: 2013-01-26 18:06:32 @D : no, my comment was posted after 12:31:18, (after the update) ... Now the problem should land in tutorial, solution is very very easy (and in the same time seems impossible in Python even with the new time limit). More, test cases are weak. Last edit: 2013-01-26 18:07:24
	:D: 2013-01-26 17:48:16 Thanks for the update! Don't blame author for missing comments. I could be due to problem updates. Last edit: 2013-01-26 17:49:07
	Francky: 2013-01-26 14:02:55 @psetter : why my message was deleted ??? :-( So, I'll set a harder edition, this one is too easy and (in the same time) probably impossible in Python. Edit. @all : That's done -> GUMATH2, certified Python feasible, with much higher constraints. Have fun ;-) EDIT2 : my comment (masked, not deleted) had been unmasked. I'll edit my problem title as "medium", (it's not hard imho). Last edit: 2013-01-27 08:20:30
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-01-26 13:28:48 @Francky: Awesome Idea :-D please set that problem for me, Interesting... ;-)
	Francky: 2013-01-26 23:00:36 @psetter : You should put Nmax at 10^18, and keep intact all others constraints. But it will make another change :-( One possibility would to put this one in tutorial (as it is too simple) and make a classical edition with Nmax at 10^18. If you can't make it, just tell me, I'll do it. @others : what about this idea ? @Francky Mark this one as easy and new problem as hard.I'll make it. Last edit: 2013-01-26 23:03:27
	Sandeep Singh Jakhar: 2013-01-26 11:31:18 @everyone The limit's are changed.
	:D: 2013-01-30 08:43:53 Ok, time limit is absurd here. Don't care that it's doable. You can get different results depending on the run, because of time measurements erros. Also it seem it's been cut down since yesterday, to make it barely doable. Probably if you retested current AC solutions some of them would TLE. Hidden until increased to at least 0.5s, preferable 1s. If you want to make it a sensible challenge increase T and L limits. Remove the Hidden Flag now. Last edit: 2013-01-26 11:30:53

Submit solution!

Added by:	Sandeep Singh
Date:	2013-01-25
Time limit:	0.100s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64