在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)Fib_0=0,Fib_1=1,Fib_n=Fib_{n−1}+Fib_{n−2}(n>1)Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)。
给定整数 nnn，求Fibn mod 10000 Fib_n \bmod10000Fibnmod10000。
输入包含不超过 100 组测试用例。
每个测试用例占一行，包含一个整数 nnn。
当输入用例 nnn=−1 时，表示输入终止，且该用例无需处理。
每个测试用例输出一个整数表示结果。
每个结果占一行。
0 9 999999999 1000000000 -1
0 34 626 6875
0≤n≤2×1090≤n≤2×10^90≤n≤2×109
注册一个 HOJ 通用账户，您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 HOJ 通用账户
