Zar1

#include <iostream>
#define MOD 1000000007
#define LL long long int
using namespace std;
LL n;
struct Mat
{
    int mat[6][6];
};
Mat NullMat=
{
    {
        {1,0,0,0,0,0},
        {0,1,0,0,0,0},
        {0,0,1,0,0,0},
        {0,0,0,1,0,0},
        {0,0,0,0,1,0},
        {0,0,0,0,0,1}
    }
};

Mat InitMat=
{
    {
        {0,1,0,0,0,0},
        {0,0,1,0,0,0},
        {0,0,0,1,0,0},
        {0,0,0,0,1,0},
        {0,0,0,0,0,1},
        {1,1,1,1,1,1}
    }
};

Mat prod(Mat A,Mat B)
{
    Mat C;
    for(int i=0;i<6;++i)
        for(int j=0;j<6;++j)
        {
            C.mat[i][j]=0;
            for(int k=0;k<6;++k)
                C.mat[i][j]=(1ULL*C.mat[i][j]+1ULL*A.mat[i][k]*B.mat[k][j]%MOD)%MOD;
            C.mat[i][j]%=MOD;
        }
    return C;
}

Mat pwr(Mat A,LL n)
{
    Mat R=NullMat;
    while(n)
    {
        if(n%2)
            R=prod(R,A);
        A=prod(A,A);
        n/=2;
    }
    return R;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    Mat C=pwr(InitMat,n);
    cout<<C.mat[5][5];
    return 0;
}