【题目描述】 原题来自：POJ 3070

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

求 Fnmod104 。

【输入】 多组数据，每组数据一行，一个整数 n。

输入以 −1 结束。

【输出】 对于每组数据，输出 Fnmod104 。

【输入样例】
0
9
999999999
1000000000
-1
【输出样例】
0
34
626
6875

对于全部数据，$0≤n≤10^9$ 。