题目描述
原题来自：POJ 3070
我们知道斐波那契数列
F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}
F0
=0,F1
=1,Fn
=Fn−1
+Fn−2
。
求
F_n\bmod 10^4
Fn
mod104。
输入
多组数据，每组数据一行，一个整数
n
n。
输入以
-1
−1 结束。
输出
对于每组数据，输出
F_n\bmod 10^4
Fn
mod104。
样例输入
0
9
999999999
1000000000
-1
样例输出
0
34
626
6875
提示
数据范围与提示
对于全部数据，
0\le n\le 10^9
0≤n≤109。
来源/分类
ybttg 矩阵