#10223. 「一本通 6.5 练习 1」Fibonacci

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 1bentong

题目描述

原题来自:POJ 3070

我们知道斐波那契数列 F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}

F_n\bmod 10^4

输入格式

多组数据,每组数据一行,一个整数 n

输入以 -1 结束。

输出格式

对于每组数据,输出 F_n\bmod 10^4

样例

样例输入

0
9
999999999
1000000000
-1

样例输出

0
34
626
6875

数据范围与提示

对于全部数据, 0\le n\le 10^9