20分求解qwq

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <queue>
#define maxn 3
#define mo 1000000007
using namespace std;

long long n;

struct matrix
{ 
    long long m[maxn][maxn];
    void clear()
    {
    	for(int i=1;i<maxn;++i)
    	for(int j=1;j<maxn;++j)
    	    m[i][j]=0;
	}
}a,b,e;

long long read()
{
	long long xx=0,kk=1;char p='-';
	while(!isdigit(p)){p=getchar();if(p=='-')kk=-1;}
	while(isdigit(p)){xx=xx*10+p-'0';p=getchar();}
	return kk*xx;
}

matrix mul(matrix a,matrix b)
{
	matrix c;c.clear();
	for(int i=1;i<maxn;++i)
	for(int j=1;j<maxn;++j)
	for(int k=1;k<maxn;++k)
	    c.m[i][j]=(c.m[i][j]+((a.m[i][k]%mo)*(b.m[k][j]%mo))%mo)%mo;
	return c;
}

matrix poww(matrix a,long long b)
{
	matrix base=a,ans=e;
	while(b)
	{
		if(b&1)ans=mul(base,ans);
		base=mul(base,base);
		b>>=1;
	}
	return ans;
}

int main()
{
	n=read();
	a.clear();b.clear();e.clear();
	a.m[1][1]=a.m[1][2]=1;
	b.m[1][1]=b.m[1][2]=b.m[2][1]=1;
	e.m[1][1]=e.m[2][2]=1;
    matrix ans=mul(poww(b,n-1),a);
    printf("%lld\n",ans.m[1][1]);
    return 0;
}