#描述#
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函数。

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

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

#样例1#
##样例输入1##

6 4 0

##样例输出1##

30
2

#限制#
100ms
32768KB

#提示#

#来源#
qianneng