题目描述

给定一个整数n，输出第n项斐波那契数列的值。 用f[i]表示斐波那契数列的第i项取余10000的值，f[i] = f[i - 1] + f[i - 2], f[1] = 1, f[2] = 1; 请注意数据范围

输入格式

若干行，若干个正整数n，输入以-1结束

输出格式

若干行，每行对于一个整数为f[n]MOD10000的值

样例

1
3
-1

1
2

数据范围与提示

20% : n <= 25;

40% : n <= 1e7;

60% : n <= 1e14;

100% : n在long long范围内;