矩阵快速幂

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e6+5;
typedef long long ll;
const ll mod=1000000007;
struct mat{
    ll m[2][2];
};
mat mul(mat a,mat b){
    mat c;
    memset(c.m,0,sizeof(c.m));
    for(int i=0;i<2;i++)
       for(int j=0;j<2;j++){
               for(int k=0;k<2;k++)
            c.m[i][j]+=a.m[i][k]*b.m[k][j];
            c.m[i][j]%=mod;
       }

    return c;
}
mat Qpow(mat a,ll n){
    mat ans;
    memset(ans.m,0,sizeof(ans.m));
    for(int i=0;i<2;i++)
      ans.m[i][i]=1;
    while(n){
        if(n&1)
           ans=mul(ans,a);
        a=mul(a,a);
        n>>=1;
    }
    return ans;
}
int main(){
    int n;
    while(cin>>n&&n!=-1){
        mat a;
    a.m[0][0]=a.m[0][1]=a.m[1][0]=1;a.m[1][1]=0;
    a=Qpow(a,n,2);
    /*for(int i=0;i<2;i++){
        for(int j=0;j<2;j++)
         printf("%lld ",a.m[i][j]);
        printf("\n");
    }*/
    printf("%lld\n",a.m[0][1]);
   } 
       return 0; 
}