Sang-geun's Lock

A certain lock uses a 9-digit number as its password. When you touch the lock, its LED display shows a single integer $N$. The lock opens once you enter the last 9 digits of the number of trees that satisfy the condition below.

Consider binary trees with $N$ nodes. For every node, the difference between the heights of its left and right subtrees must be at most $1$. The height of a subtree is the length of the longest path from that subtree's root down to a leaf. A subtree consisting of a single node has height $0$, and an empty subtree (no nodes) has height $-1$.

Count how many distinct tree shapes there are.

The input consists of several test cases. Each test case is a single integer $N$ with $1 \le N \le 1427$. Input continues until the end of the file.

For each test case, print on its own line the last 9 digits of the number of trees corresponding to the given $N$. If the value has fewer than 9 digits, pad it with leading zeros so that exactly 9 digits are printed.