PB - Parking Bay

no tags 

Illustration 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 S1 to Sn enter the parking bay. Each rebel Ri heads to his favorite parking slot Pi, 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 Pi 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 Ai%10007, where Ai is the number of sequences in the ith 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: 2018-06-16 07:56:57

pen paper is basic requirement for solving this question............

ayushgupta1997: 2018-06-02 23:37:53

Explore about Parking Functions it's interesting!

azam_9: 2016-07-04 11:51:52

use the formula ( (n+1)^(n-1) )%10007 and its done..happy coding..:P

Last edit: 2016-07-04 11:52:05
aryan_r: 2016-06-27 14:58:50

Here is just one more test case in Order to understand it better :
n=3 Sequences: 111 112 121 211 113 131 311 122 212 221 123 132 231 321 213 312 (16)
Solve for others :) Hope this helps!

: 2014-04-20 10:40:22

@kashyap .it is not clear what does problem state.Could u plz clearify my doubt

unXled: 2012-07-15 11:39:08

anyone plz tell the answer for n=7 and n=1000000

Mahesh Chandra Sharma: 2010-05-06 08:58:12

@kalini he cant shift left, only right shifing is possible

suteerth: 2010-04-06 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: 2010-04-06 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: 2009-06-18 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:2006-10-10
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 PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM qobi SCM guile ST WHITESPACE
Resource:Fair Isaac Programming Challenge - prelims 2006