2637: Fibonacci

内存限制：512 MB 时间限制：1.000 S
评测方式：文本比较 命题人：
提交：0 解决：0

题目描述

原题来自：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 ≤ n ≤ 10^9$ 。

来源/分类

提交提交记录统计讨论露一手!