斐波那契数列的定义如下：
F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n >= 2)
(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...)
给出n，求F(n)，由于结果很大，输出F(n) % 1000000009的结果即可。
输入
输入1个数n(1 <= n <= 10^18)。
输出
输出F(n) % 1000000009的结果。
输入样例
11
输出样例
89
解：由于斐波那契数列的第N（N>2）项等于N-1个{{1，1}，{1，1}}矩阵相乘后的第一项。
由于这种矩阵形式上的特殊性（对称，乘法可交换），我们可以借助快速幂的思想可以快速求解这个答案。
#include <stdio.h> #define MOD 1000000009 int main()
{
long long n;
while (scanf_s("%lld", &n) != EOF)
{
long long a[][] = { ,,, }, tmp[][] = { ,,, };
if (n < )printf("%d\n", n);
else
{
--n;
while (n)
{
if (n % )
{
int q, w, e;
q = (tmp[][] * a[][] + tmp[][] * a[][]) % MOD;
w = (tmp[][] * a[][] + tmp[][] * a[][]) % MOD;
e = (tmp[][] * a[][] + tmp[][] * a[][]) % MOD;
a[][] = q;
a[][] = a[][] = w;
a[][] = e;
}
int q, w, e;
q = (tmp[][] * tmp[][] + tmp[][] * tmp[][]) % MOD;
w = (tmp[][] * tmp[][] + tmp[][] * tmp[][]) % MOD;
e = (tmp[][] * tmp[][] + tmp[][] * tmp[][]) % MOD;
tmp[][] = q;
tmp[][] = tmp[][] = w;
tmp[][] = e;
n >>= ;
}
printf("%d\n", a[][]);
}
}
}