#include <bits/stdc++.h>
using namespace std; 
#define int long long
const int mod=1e9+7;
int n;
int as;
int cs[2][20],zs[20][20];
struct mat{
	int x,y,a[20][20];
	mat(int n=0,int m=0){x=n;y=m;memset(a,0,sizeof(a));}
	mat(int n,int m,int c[20][20]){x=n;y=m;memcpy(a,c,sizeof(a));}
	static mat unit(int n){
		mat res=mat(n,n);
		for(int i=1;i<=n;i++) res.a[i][i]=1;
		return res;
	}
	mat operator *(const mat &A)const{
		mat res=mat(x,A.y);
		for(int i=1;i<=x;i++){
			for(int j=1;j<=A.y;j++){
				for(int k=1;k<=y;k++) res.a[i][j]=(res.a[i][j]+a[i][k]*A.a[k][j]%mod)%mod;
			}
		}
		return res;
	}
	mat operator ^(int b)const{
		mat res=unit(x),a=*this;
		while(b){
			if(b&1) res=res*a;
			a=a*a;
			b>>=1;
		}
		return res;
	}
};
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=10;i++){
		cs[1][i]=1;
		for(int D=-2;D<=2;D++) 
			if(i+D>=1&&i+D<=10) zs[i+D][i]=1; 
	}
	mat ans=mat(1,10,cs)*(mat(10,10,zs)^(n-1));
	for(int i=2;i<=10;i++) as=(as+ans.a[1][i])%mod;
	if(n==1) as++;
	printf("%lld",as);
	return 0;
}

开 O2 RE，不开 AC。

提交记录：
不开 O2：AC
开：RE