题目描述

在斐波那契数列中，$\red{Fib_0 = 0 , Fib_1 = 1 , Fib_n = Fib_{n−1} + Fib_{n−2} (n>1) }$。

给定整数 $\red n$，求 $\red {Fib_n}$ $\red{Mod}$ $\red{10000}$。

输入格式

输入包含多组测试用例。

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

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

输出格式

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

每个结果占一行。

样例

输入样例

0
9
999999999
1000000000
-1

输出样例

0
34
626
6875

提示

$\red{0≤n≤2\times 10^9}$