第05次上机实验题目（分治策略）#

---

利用分治策略设计算法，编程解决下列问题

Fibonacci数列的定义为：

$$F_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F_{n-1} + F_{n-2} & n \ge 2 \end{cases}$$

问题描述#

在 Fibonacci 数列中，其前十项是：$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$。

根据分治策略，求解 Fibonacci 数列的矩阵幂公式是：

$$\begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n$$

给定一个整数 $n$，请你计算 $F_n$ 在十进制表示下的最后四位。

输入格式#

输入将包含一个测试用例。每个测试用例仅有一行，包含一个整数n（其中0≤n≤109)。

输出格式#

对于每个测试用例，输出Fn的最后四位数字。如果Fn的最后四位都是零，则输出0；否则，省略任何前导零（即，输出Fn mod 10000）。

样例输入#

0

样例输出#

0

样例输入#

9

样例输出#

34