前言：f[n]=f[n-1】+f[n-2]；f[0]=0,f[1]=1;
这是斐波那契数列公式。如果要求F[N]，要计算N次；
更一般的知道其只与n有关的公式:
b=(1+sqrt(5))/2;
c=(1-sqrt(5))/2;
fn=a(b^n-c^n);(不会Latex的痛，
如果答案是Mod的话，运算时有问题的，当然可以矩阵快速米之类的。
但是我说一种数学上的傻逼方法。
如果mod 是一个素数，而且mod=5k+1或者mod=5k-1;
那么讲会有简洁方法；
构造一个等式 x*x-x-1=0 其解刚好是b,a;
结论对于一个这样的Mod一定能找打在Zp下的平方根(http://math.stackexchange.com/questions/523351/square-root-of-5-in-modulo-prime-field
比如：mod=99991
x*x-x-1(%99991)==(x-55048*(x-44944)%99991=x^2-99992x+2474077312(%99991);
所以求解的时候愉快的快速米，逆元就好了。可能你会说还是没构造矩阵来的快。
引入一个问题：求前n的斐波那契数列的sum%1000000009的值，n<=1000000009;
怎么做？
构造矩阵似乎比较难构造。
如果找到a,b即能sqrt(5)%10^9+7的话似乎就是等比数列
10^9+9的 a,b分别是
fn=(a^n-b^n)/(a-b) 【a,b的值是前面的】
那么Sn=f1+f2+f3+...fn;
=a^1+a^2+a^3+...a^n-b^1-b^2-...b^n/(a-b) % mod ;
=(a^(n+1)-a)/(a-1)-{(b^(n+1)-b} /(b-1) / (a-b) ;
这些都很好求啊。
还有一些在其他运用上