You know YaoYao is fond of his chains. He has a lot of chains and each chain has n diamonds on it. There are two kinds of diamonds, labeled 0 and 1. We can write down the label of diamonds on a chain. So each chain can be written as a sequence consisting of 0 and 1. We know that chains are different with each other. And their length is exactly n. And what’s more, each chain sequence doesn’t contain “101” as a substring. Could you tell how many chains will YaoYao have at most?

There will be multiple test cases in a test data. For each test case, there is only one number n(n<10000). The end of the input is indicated by a -1, which should not be processed as a case.

For each test case, only one line with a number indicating the total number of chains YaoYao can have at most of length n. The answer should be print after module 9997.

We can see when the length equals to 4. We can have those chains: 0000,0001,0010,0011 0100,0110,0111,1000 1001,1100,1110,1111

multi