1645：Fibonacci

题目描述

我们知道斐波那契数列 $F_0=0, F_1=1, F_n = F_{n-1} + F_{n-2}$。

求 $F_n \bmod 10^4$。

输入格式

多组数据，每组数据一行，一个整数 $n$。

输入以 $-1$ 结束。

输出格式

对于每组数据，输出 $F_n \bmod 10^4$。

样例

样例输入 #1

0
9
999999999
1000000000
-1

样例输出 #1

0
34
626
6875

样例解释 #1

• $F_0 = 0$，输出 $0$。
• $F_9 = 34$（因为 $F_0=0, F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, F_7=13, F_8=21, F_9=34$），输出 $34$。
• $F_{999999999} \bmod 10000 = 626$。
• $F_{1000000000} \bmod 10000 = 6875$。

数据范围

对于全部数据，$0 \le n \le 10^9$。

时空限制

• 时间限制：1000 ms
• 内存限制：524288 KB

注意：$n$ 很大，需要使用矩阵快速幂计算 Fibonacci 数列。递推矩阵为：

$$M = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$$

则有：

$$\begin{bmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{bmatrix} = M^n$$

因此，$F_n$ 是 $M^n$ 的右上角（或左下角）元素。

具体地，计算 $M^n$，然后取右上角元素即可。注意 $n=0$ 时，$M^0$ 是单位矩阵，右上角为 $0$，即 $F_0=0$。

由于模数 $10000$ 较小，矩阵元素在计算过程中取模即可。矩阵快速幂复杂度 $O(2^3 \log n) = O(8 \log n)$，可以接受。

注意多组数据，直到输入 $-1$ 结束。