题目描述

在斐波那契数列中，$F_0=0$, $F_1=1$, $F_n = F_{n-1} + F_{n-2} \; (n>1)$。

给定整数 $n$，求 $F_n \bmod 10000$。

输入格式

输入包含不超过 $100$ 组测试用例。

每个测试用例占一行，包含一个整数 $n$。

当输入用例 $n=-1$ 时，表示输入终止，且该用例无需处理。

输出格式

每个测试用例输出一个整数表示结果。

每个结果占一行。

样例

输入样例：

0
9
999999999
1000000000
-1

输出样例：

0
34
626
6875

样例解释

• $F_0 = 0$，输出 0。
• $F_9 = 34$，输出 34。
• $F_{999999999} \bmod 10000 = 626$。
• $F_{1000000000} \bmod 10000 = 6875$。

数据范围

• $0 \le n \le 2 \times 10^9$

时空限制

• 时间限制：1 秒
• 空间限制：64 MB