题目描述

斐波那契数列是一个经典的数列，其定义如下：$F_0 = 0, F_1 = 1$, 且对于 $n > 1$，有 $F_n = F_{n-1} + F_{n-2}$。现在，给定一个整数 $n$，要求计算 $F_n$ 对 $10000$ 取模的结果。

输入格式

输入包含多组测试用例。

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

当输入为 $n = -1$ 时，表示输入结束，且该组数据无需处理。

输出格式

对于每组测试用例，输出一个整数，表示 $F_n$ $mod$ $10000$ 的结果。每个结果占一行。

样例

0
9
999999999
1000000000
-1

0
34
626
6875

提示

数据范围

• 对于 $100 \%$的测试样例，有 $0 ≤ n ≤ 2 × 10^9$