题目描述

在斐波那契整数序列中，$F_0 = 0$，$F_1 = 1$，对于 $n \geq 2$，$F_n = F_{n-1} + F_{n-2}$。例如，斐波那契数列的前十项为：

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \ldots$

斐波那契数列的另一种计算公式为：

.

给定一个整数 $n$，你的目标是计算 $F_n$ 的最后4位数字。

输入

输入测试文件包含多个测试用例。每个测试用例由一行组成，包含一个整数 $n$（其中 $0 \leq n \leq 1,000,000,000$）。文件末尾由一行单独的 $-1$ 表示。

输出

对于每个测试用例，输出 $F_n$ 的最后4位数字。如果 $F_n$ 的最后4位数字全为零，则输出 0；否则，省略任何前导零（即输出 $F_n \mod 10000$）。

输入样例1

0
9
999999999
1000000000
-1

输出样例1

0
34
626
6875

提示

提醒一下，矩阵乘法是满足结合律的，两个 $2 \times 2$ 矩阵的乘积由以下公式给出：

.

此外，任何 $2 \times 2$ 矩阵的0次幂都等于单位矩阵：

.

来源

斯坦福本地赛 2006