題目 2541:
信息學奧賽一本通T1645-Fibonacci
時間限制: 2s
內存限制: 192MB 提交: 23 解決: 13
題目描述
原題來自：POJ 3070
我們知道斐波那契數(shù)列 F0=0,F1=1,Fn=Fn?1+Fn?2。
求 Fn mod 104 。
輸入格式
多組數(shù)據(jù)，每組數(shù)據(jù)一行，一個整數(shù) n。
輸入以 ?1 結束。
輸出格式
對于每組數(shù)據(jù)，輸出 Fn mod 104 。
樣例輸入
0
9
999999999
1000000000
-1
提示
數(shù)據(jù)范圍與提示：
對于全部數(shù)據(jù)，0≤n≤109 。