题目描述

我们知道斐波那契数列$F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2}$。 求$F_n \bmod10^4$。

输入描述

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

输出描述

对于每组数据，输出$F_n \bmod10^4$。

示例1

输入

0
9
999999999
1000000000
-1

输出

0
34
626
6875

备注

输入样例 #2

0
9
999999999
1000000000
804289385
846930887
681692779
714636917
957747795
424238336
719885387
649760494
596516650
189641423
25202364
350490029
783368691
102520061
44897766
967513928
365180542
540383428
304089173
303455738
35005212
521595369
294702568
726956431
336465783
861021531
278722863
233665124
145174070
468703136
101513931
801979804
315634024
635723059
369133071
125898169
59961395
89018459
628175012
656478044
131176231
653377375
859484422
914544921
608413785
756898538
734575200
973594326
149798316
38664373
129566415
184803527
412776092
424268982
911759958
749241874
137806863
42999171
982906997
135497282
511702306
84420928
937477086
827336329
572660337
159126507
805750847
632621731
100661315
433925859
141616126
84353896
939819583
1100548
998898816
548233369
610515435
585990366
374344045
760313751
477171089
356426809
945117277
889947180
780695790
709393585
491705404
918502653
752392755
474612401
53999935
264095062
411549678
843993370
943947740
984210014
-1

输出样例 #2

0
34
626
6875
1885
2833
8021
4997
5330
3077
5833
8367
1575
8257
8448
4229
834
9461
2888
1861
2671
4611
9493
6769
544
5794
6891
3869
5922
5394
9042
5693
7385
677
6994
7603
1243
5541
2754
9969
6105
1641
8269
4733
7069
125
8911
9346
9410
1169
6400
4168
3712
9193
4210
9793
8429
9416
5704
807
5042
5154
3877
3441
1783
9611
5048
2529
4242
9138
6273
4069
6185
8866
6943
5547
5997
4851
9712
3169
2690
1688
1545
1874
189
8209
6457
1760
3720
3585
4803
2898
370
5901
7565
1631
2264
8535
1805
377

输入样例 #3

1
2
-1

输出样例 #3

1
1

数据范围

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