输出全是0，

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int MOD=1000;
struct Node
{
	long long a[10][10];
	void mem()
	{
		memset(a,0,sizeof(a));
	}
};
Node operator * (const Node &aa,const Node &b)
{
	Node z;
	z.mem();
	for(int i=1;i<=8;i++)
	{
		for(int j=1;j<=8;j++)
		{
			for(int k=1;k<=8;k++)
			{
				z.a[i][j]=(z.a[i][j]+(aa.a[i][k]*b.a[k][j])%MOD)%MOD;
			}
		}
	}return z;
}
Node kuaisu(Node firs,int N)
{
	Node danwei;
	danwei.mem();
	danwei.a[1][1]=1;
	while(N>0)
	{
		if(N&2)
		{
			danwei=danwei*firs;
		}
		firs=firs*firs;
		N/=2;
	}
	return danwei;
}
int main()
{
	int N;
	cin>>N;
	Node firs; 
	firs.mem();
	for(int i=2;i<8;i++)
	{
		if(i!=5)
		{
			firs.a[i][i+1]=1;
			firs.a[i][i-1]=1;
		}
	}
	firs.a[1][8]=1;
	firs.a[8][1]=1;
	firs.a[1][2]=1;
	firs.a[8][7]=1;
	Node l=kuaisu(firs,N);
	cout<<l.a[1][5];
	return 0;
}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int MOD=1000;
struct Node
{
	long long a[10][10];
	void mem()
	{
		memset(a,0,sizeof(a));
	}
};
Node operator * (const Node &aa,const Node &b)
{
	Node z;
	z.mem();
	for(int i=1;i<=8;i++)
	{
		for(int j=1;j<=8;j++)
		{
			for(int k=1;k<=8;k++)
			{
				z.a[i][j]=(z.a[i][j]+(aa.a[i][k]*b.a[k][j])%MOD)%MOD;
			}
		}
	}return z;
}
Node kuaisu(Node firs,int N)
{
	Node danwei;
	danwei.mem();
	danwei.a[1][1]=1;
	while(N>0)
	{
		if(N&2)
		{
			danwei=danwei*firs;
		}
		firs=firs*firs;
		N/=2;
	}
	return danwei;
}
int main()
{
	int N;
	cin>>N;
	Node firs; 
	firs.mem();
	for(int i=2;i<8;i++)
	{
		if(i!=5)
		{
			firs.a[i][i+1]=1;
			firs.a[i][i-1]=1;
		}
	}
	firs.a[1][8]=1;
	firs.a[8][1]=1;
	firs.a[1][2]=1;
	firs.a[8][7]=1;
	Node l=kuaisu(firs,N);
	cout<<l.a[1][5];
	return 0;
}