Problem1223--「一本通 6.5 练习 1」Fibonacci

1223: 「一本通 6.5 练习 1」Fibonacci

Time Limit: 1 Sec  Memory Limit: 512 MB
Submit: 0  Solved: 0
Submit Status Web Board

Creator:

Description

原题来自:POJ 3070

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

Fn mod 104F_n\bmod 10^4Fnmod104


Input

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

输入以 −1-11 结束。


Output

对于每组数据,输出 Fn mod 104F_n\bmod 10^4Fnmod104


Sample Input

0
9
999999999
1000000000
-1

Sample Output

0
34
626
6875

HINT

对于全部数据,0≤n≤1090\le n\le 10^90n109


Source/Category


Submit Status