我们知道斐波那契数列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=Fn−1+Fn−2。 求Fn mod 104F_n \bmod10^4Fnmod104。
多组数据，每组数据一行，一个整数n。 输入以-1结束。
对于每组数据，输出Fn mod 104F_n \bmod10^4Fnmod104。
0 9 999999999 1000000000 -1
0 34 626 6875
对于全部数据，0≤n≤1090 \leq n \leq 10^90≤n≤109。
注册一个 珅泽OJ 通用账户，您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 珅泽OJ 通用账户
