PB  Parking Bay
Luke Skywalker successfully leads the rebel starship fleet to break the Emperor's siege of the planet Endor. The rebels, jubilant in their victory, return to their base on the moon of Endor to pay their homage to Princess Leia. They fly towards the parking bay where there are n parking slots in a row. One by one n starships numbered S_{1} to S_{n} enter the parking bay. Each rebel R_{i} heads to his favorite parking slot P_{i}, and if it is free, he docks his starship there. Otherwise, he continues further to the next free slot and occupies it. But if all succeeding slots are occupied, he leaves for good. How many sequences P_{i} are such that every rebel can dock his starship?
Input Description
The first line of the input is a positive integer t ≤ 20, which is the number of test cases. The descriptions of the test cases follow one after the other. The description of each test case contains exactly one line (a positive integer), containing the value of n ≤ 1000000.
Output Description
The output consists of exactly t lines. The ith line should be A_{i}%10007, where A_{i} is the number of sequences in the i^{th} case, and 'x%y' represents the remainder when x is divided by y.
Example
Input
2
1
2
Output
1
3
Explanation: In the given example, 11, 12 and 21 are the possible sequences.
hide comments
sherlock11:
20180616 07:56:57
pen paper is basic requirement for solving this question............ 

ayushgupta1997:
20180602 23:37:53
Explore about Parking Functions it's interesting! 

azam_9:
20160704 11:51:52
use the formula ( (n+1)^(n1) )%10007 and its done..happy coding..:P Last edit: 20160704 11:52:05 

aryan_r:
20160627 14:58:50
Here is just one more test case in Order to understand it better :


:
20140420 10:40:22
@kashyap .it is not clear what does problem state.Could u plz clearify my doubt 

unXled:
20120715 11:39:08
anyone plz tell the answer for n=7 and n=1000000 

Mahesh Chandra Sharma:
20100506 08:58:12
@kalini he cant shift left, only right shifing is possible 

suteerth:
20100406 19:51:27
By using the logic used for 11, I can then even say that 22 is a valid sequence where both wants 2, the first rebel will park at the leftmost 2 and the other will settle for the spot left, thus making the total count 4. 

suteerth:
20100406 19:49:08
When it clearly says that Ri will want to park in the slot Pi, how can there be two slots marked 1. The slots have to be marked from 1 to n, and having slots of the same name invalidates what has been explained. 

Pavel Kazatsker:
20090618 19:22:12
in example 2, there are two pilots; they can each choose place to park and the only fail condition is if they both choose the second slot. 11 means that they both want to park in the first slot 
Added by:  Kashyap KBR 
Date:  20061010 
Time limit:  0.524s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PASGPC PASFPC PERL PHP PIKE PRLGswi PYTHON RUBY SCM qobi SCM guile ST WHITESPACE 
Resource:  Fair Isaac Programming Challenge  prelims 2006 