#T1645. 「一本通 6.5 练习 1」Fibonacci

「一本通 6.5 练习 1」Fibonacci

题目描述

原题来自:POJ 3070

我们知道斐波那契数列 F_0=0,F_1=1,F_n=F_n1+F_n2F\_0=0,F\_1=1,F\_n=F\_{n-1}+F\_{n-2}

F_nbmod104F\_n\\bmod 10^4

输入

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

输入以 1-1 结束。

输出

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

样例

0
9
999999999
1000000000
-1
0
34
626
6875

提示

数据范围与提示:

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

来源

一本通在线评测