## PB - Parking Bay

no tags

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.