输出8位数

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<set>
#include<map>
using namespace std;
#define int long long
int a[11][11]={{0,0,0,0,0,0,0,0,0,0,0},{0,1,1,1,0,0,0,0,0,0,0},{0,1,1,1,1,0,0,0,0,0,0},{0,1,1,1,1,1,0,0,0,0,0},{0,0,1,1,1,1,1,0,0,0,0},{0,0,0,1,1,1,1,1,0,0,0},{0,0,0,0,1,1,1,1,1,0,0},{0,0,0,0,0,1,1,1,1,1,0},{0,0,0,0,0,0,1,1,1,1,1},{0,0,0,0,0,0,0,1,1,1,1},{0,0,0,0,0,0,0,1,1,1}};
	int b[11][11],c[11][11];
	int h[1][10]={0,1,1,1,1,1,1,1,1,1};
	int hh[1][10];
const int mod = 1e9+7;
//int dfs(int pos,int x,int flag1,int flag2){
//	if(pos==i){
//		return 1;
//	}
//	if(!flag1&&!flag2&&dp[pos][x]!=-1){
//		return dp[pos][x];
//	}
//	int mx=9;
//	if(flag2){
//		mx=a[pos+1];
//	}
//	int ans=0;
//	for(int i=0;i<=mx;i++){
//		if(abs(i-x)<=2||flag1)
//		ans+=dfs(pos+1,i,(i==0)&flag1,flag2&(i==a[pos+1]));
//	}
//	if(flag1||flag2){
//		return ans;
//	}
//	else{
//		return dp[pos][x]=ans;
//	}
//}
signed main(){
		int k;
		cin>>k;
	while(k){
		if(k%2){
		for(int i=1;i<=10;i++){
			for(int j=1;j<=10;j++){
				for(int kk=1;kk<=10;kk++){
					b[i][j]=(b[i][j]+a[i][kk]*a[kk][j])%mod;
				}
			}
		}
	}
	k/=2;
	for(int i=1;i<=10;i++){
		for(int j=1;j<=10;j++){
			for(int kk=1;kk<=10;kk++){
				c[i][j]=(c[i][j]+a[i][kk]*a[kk][j])%mod;
			}
		}
	}
	for(int i=1;i<=10;i++){
		for(int j=1;j<=10;j++){
			a[i][j]=c[i][j];
		}
	}
	memset(c,0,sizeof(c));
	}
	
	int ans=0;
	for(int i=1;i<=10;i++){
		for(int kk=1;kk<=10;kk++){
			hh[1][i]=(b[kk][i]*h[1][kk]+hh[1][i])%mod;
		}
		ans+=hh[1][i];
		ans%=mod;
	}
	cout<<ans;
    return 0;
}