Description

YAOYAO很喜欢她的项链，她有很多项链，每个项链有N个钻石镶嵌在上面。现在有两种钻石，分别用0和1来表示。我们可以将一条项链用它上面的钻石来表示。所以每条项链都用一个含有0和1的字符串表示出来。不同的项链用0和1表示出来的字串也不同。但他们的长度都恰好是N。另外还有，每个项链都不能含有”101”作为子串。

YAOYAO想知道最多有几种不同项链他可能拥有？

Input

多组测试数据 每组测试数据仅含有一个数字N，输入数据以一个 -1 结束(不需要计算这组的答案)。

Output

对于每组测试数据 输出一个数字代表长度为N的项链最多可能的情况。由于数据很大，请将答案对9997求余以后输出。

Sample Input

3
4
-1

Sample Output

7
12

HINT

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

Source