该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

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

给定整数 $n$，求 $Fib_n$ $mod$ $10000$。

输入格式

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

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

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

输出格式

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

每个结果占一行。

数据范围

$0≤n≤2×10^9.$

输入样例:

0
9
999999999
1000000000
-1

输出样例：

0
34
626
6875