const int MOD=1e9+7;

int T;
int a[3],f[3][3];

void mul_k(int a1[3],int f1[3][3])
{
	int C[3];
	memset(C,0,sizeof C);
	rep(j,0,2)
	{
		rep(k,0,2)
		{
			C[j]=(C[j]+a1[k]*f1[k][j])%MOD;
		}	
	}
	memcpy(a,C,sizeof C);
}

void mul_self(int f1[3][3])
{
	int C[3][3];
	memset(C,0,sizeof C);
	rep(i,0,2)rep(j,0,2)rep(k,0,2)
	{
		C[i][j]=(C[i][j]+f1[i][k]*f1[k][j])%MOD;
	}
	memcpy(f,C,sizeof C);
}

void clear()
{
	rep(i,0,2)rep(j,0,2)f[i][j]=0;
	rep(i,0,3)a[i]=0;
	a[0]=1,a[1]=1,a[2]=1;
	f[0][0]=f[0][2]=f[1][0]=f[2][1]=1;
}

void solve()
{
	int n;
	cin>>n;
	if(n<=3)
	{
		cout<<1<<endl;xx;
	}
	n-=3;
	for(;n;n>>=1)
	{
		if(n&1)mul_k(a,f);
		mul_self(f);
	}
	cout<<a[0]%MOD<<endl;
	xx;
}

输出与第一个数据一致但 $0pts$