我们知道斐波那契数列 F0=0,F1=1,Fn=Fn−1+Fn−2。
求 Fn mod 10⁴ 。

多组数据，每组数据一行，一个整数 n。
输入以 −1 结束。

对于每组数据，输出 Fn mod 10⁴ 。

0
9
999999999
1000000000
-1

0
34
626
6875