Problem H
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 27 Accepted Submission(s) : 2
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
A heap is a full binary tree; for each node, its key is greater than its two sub-node’s key. Two heaps are different if there are two nodes which have different keys at the same location. Now we have a problem for you: tell me how many different N-Nodes heaps we can make with N integers?
Input
There are many test cases; for each test case, one line contains only one integer N (1<=N<=1000000) indicating how many nodes the heap has.
Output
For each test case, output one line contains an integer indicating the number of the kinds of the heaps. Because the result might be very large, you can just output the result modular 20000003.
Sample Input
1 2 3
Sample Output
1 1 2