Rank

Time Limit: 1000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2643
64-bit integer IO format: %I64d      Java class name: Main

Description

Recently in Teddy's hometown there is a competition named "Cow Year Blow Cow".N competitors had took part in this competition.The competition was so intense that the rank was changing and changing.
Now the question is:
How many different ways that n competitors can rank in a competition, allowing for the possibility of ties.
as the answer will be very large,you can just output the answer MOD 20090126.
Here are the ways when N = 2:
P1 < P2
P2 < P1
P1 = P2

Input

The first line will contain a T,then T cases followed.
each case only contain one integer N (N <= 100),indicating the number of people.

Output

One integer pey line represent the answer MOD 20090126.

Sample Input

2
2
3

Sample Output

3
13

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .