LY is a little architect, he likes to make all kinds of buildings with his building blocks. All the building blocks are the same cubes. Now he want to make a new building. He don’t want any floor of his building is disconnected. So sample of the building he likes and he dislikes like these:
The building he likes. The building he dislikes.
For example, the first building he likes because all the blocks in every line are not disconnected, while the second building he dislikes because in line 1, 3, 4, the blocks are disconnected.
Now LY has a question. If he has n building blocks, and how many different buildings he can build. We ensure that all the building blocks are in the same plane.
There are several lines in the input. Each line is a set of input data. There is only one integer n (0 < n < 1,000,000,000) means the number of blocks buildings he has. The last line of the input is a line contains 0.
For each set of input, output a single line contains one integer which is the number of different buildings he can build mod 9997.