首先要知道一个姿势，对于Fib数列这类的东西，只要取余就一定会出现循环节。所以上来就直接暴力打表找规律就好了。
MOD = 1000000007 发现循环节是 222222224。
MOD = 2222222227 发现循环节是 183120
然后这个问题就解决了。
不要问我为啥会出现循环节，我也不会证明。。。
———————————-分割线———————————-
我好像会证明了，试着证一发。
设有一个递推公式 f(n) = (f(n-1)+f(n-2))%MOD。
那么f(n) 的取值范围为[0,MOD-1]，一共MOD个数，即一共MOD×MOD种组合，，且一旦递推公式确定，这MOD个数的排列方式就确定了，所以一定存在循环节。
#include <algorithm>#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <queue>#include <cmath>#include <stack>#include <map>#pragma comment(linker, "/STACK:1024000000")#define EPS (1e-8)#define LL long long#define ULL unsigned long long#define INF 0x3f3f3f3fusing namespace std;const int MAXN = 5;struct MAT{int row,col;LL mat[MAXN][MAXN];void Init(int R,int C,int val){row = R,col = C;for(int i = 1;i <= row; ++i)for(int j = 1;j <= col; ++j)mat[i][j] = (i == j ? val : 0);}MAT Multi(MAT c,LL MOD){MAT tmp;tmp.Init(this->row,c.col,0);int i,j,k;for(k = 1;k <= this->col; ++k)for(i = 1;i <= tmp.row; ++i)for(j = 1;j <= tmp.col; ++j)(tmp.mat[i][j] += (this->mat[i][k]*c.mat[k][j])%MOD)%=MOD;return tmp;}MAT Quick(LL n,LL MOD){MAT res,tmp = *this;res.Init(row,col,1);while(n){if(n&1)res = res.Multi(tmp,MOD);tmp = tmp.Multi(tmp,MOD);n >>= 1;}return res;}void Output(){cout<<"****************"<<endl;int i,j;for(i = 1;i <= row; ++i){for(j = 1;j <= col; ++j)printf("%3d ",mat[i][j]);puts("");}cout<<"&&&&&&&&&&&&&"<<endl;}};int main(){const int M0 = 183120;const int M1 = 222222224;const int M2 = 1000000007;LL n;MAT A,B,tmp;A.Init(2,2,0);A.mat[1][1] = 0;A.mat[1][2] = 1;A.mat[2][1] = 1;A.mat[2][2] = 3;B.Init(2,1,0);B.mat[1][1] = 0;B.mat[2][1] = 1;while(cin>>n){n = A.Quick(n,M0).Multi(B,M0).mat[1][1];n = A.Quick(n,M1).Multi(B,M1).mat[1][1];n = A.Quick(n,M2).Multi(B,M2).mat[1][1];cout<<n<<endl;}return 0;}
生活的最大悲剧不是失败，而是一个人已经习惯于失败。
