# 描述

In the Fibonacci integer sequence, $F_0 = 0, F_1 = 1$, and $F_n = F_n − 1 + F_n − 2 for n ≥ 2$. For example, the first ten terms of the Fibonacci sequence are:

An alternative formula for the Fibonacci sequence is

Given an integer $n$, your goal is to compute the last 4 digits of $F_n$.

## Input

The input test file will contain multiple test cases. Each test case consists of a single line containing n (where $0 ≤ n ≤ 1,000,000,000$). The end-of-file is denoted by a single line containing the number −1.

## Output

For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

• intput

• output

# 思路

• 题目直接给出了转移矩阵，显然那个二阶常数矩阵需要用到矩阵快速幂才能求解。
• 注意单位阵和初始化。

# 代码

-------------本文结束 感谢您的阅读-------------