#586. Fibonacci

Fibonacci

题目描述

原题来自:POJ 3070

我们知道斐波那契数列 F0=0,F1=1,Fn=Fn1+Fn2F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}

Fnmod104F_n\bmod 10^4

输入格式

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

输入以 1-1 结束。

输出格式

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

样例

0
9
999999999
1000000000
-1
0
34
626
6875

数据范围与提示

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