Description

void f(int n)函数的定义为： 若n=1或2则调用g(n) 否则调用f(n-1)Xg(n-1) 而void g(int n)函数的定义为： 若n=1或2则调用1次k函数 否则调用g(n-1)+g(n-2)次k函数 当调用f(n)时，希望知道究竟调用了几次k函数。

Input

若干n，其值不大于1亿。当输入为0时，输入结束。

Output

输出对应n的f(n)函数调用中，共调用了几次k函数，并取10000的模，每个结果占一行。

Sample

Input

6 4 0

Output

30
2

Source: qianneng