#define MOD 1000000007
typedef long long ll;
typedef struct matrixnod{
    ll m[2][2];
}matrix;
matrix mat(matrix a,matrix b){
    matrix c;
    int mod=MOD-1;
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++){
            c.m[i][j]=0;
            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;
}
matrix doexpmat(matrix a,ll num){
    matrix t={
        1,0,
        0,1
    };
    while(num){
        if(num&1) t=mat(a,t);
        num=num>>1;
        a=mat(a,a);
    }
    return t;
}