H :: Tree Count

Time Limit: 5 Seconds    Memory Limit: 65536 KB

 Our superhero Carry Adder has uncovered the secret method that the evil Head Crash uses to generate the entrance code to his fortress in Oakland. The code is always the number of distinct binary search trees with some number of nodes, that have a specific property. To keep this code short, he only uses the least significant nine digits.
The property is that, for each node, the height of the right subtree of that node is within one of the height of the left subtree of that node. Here, the height of a subtree is the length of the longest path from the root of that subtree to any leaf of that subtree. A subtree with a single node has a height of 0, and by convention, a subtree containing no nodes is considered to have a height of −1.

 

Input

Input will be formatted as follows. Each test case will occur on its own line. Each line will contain only a single integer, N , the number of nodes. The value of N will be between 1 and 1427, inclusive.

Output

Your output is one line per test case, containing only the nine-digit code (note that you must print leading zeros).

Sample Input

1
3
6
21

Sample Output

000000001
000000001
000000004
000036900

Submit

Source: 2011 Pacific Northwest Region Programming Contest