题目 2541:
信息学奥赛一本通T1645-Fibonacci
时间限制: 3s
内存限制: 192MB 提交: 23 解决: 13
题目描述
原题来自：POJ 3070
我们知道斐波那契数列 F0=0,F1=1,Fn=Fn−1+Fn−2。
求 Fn mod 104 。
输入格式
多组数据，每组数据一行，一个整数 n。
输入以 −1 结束。
输出格式
对于每组数据，输出 Fn mod 104 。
样例输入
0
9
999999999
1000000000
-1
提示
数据范围与提示：
对于全部数据，0≤n≤109 。