有没有大佬帮忙优化一下qwq

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9; 
long long n;
struct jz{
	long long z[17][17];
	void to_0(){
		memset(z,0,sizeof(z));
	}
	void a_cs(){
		z[1][1]=24;
        z[1][2]=480;
        z[1][3]=7680;
        z[1][4]=107520;
	}
	void b_cs(){
		z[2][1]=1;
		z[3][2]=1;
		z[4][3]=1;
		z[1][4]=1536;
		z[2][4]=mod-320;
		z[3][4]=mod-80;
		z[4][4]=20;
	}
};
jz mul(jz a,jz b){
	jz ans;
	ans.to_0();
	for(int i=1;i<=4;i++){
		for(int j=1;j<=4;j++){
			for(int k=1;k<=4;k++){
				ans.z[i][k]=(ans.z[i][k]+a.z[i][j]*b.z[j][k])%mod;
			}
		}
	}
	return ans;
}
jz ksm(jz a,long long k){
	jz ans;
	ans.to_0();
	for(int i=1;i<=4;i++)ans.z[i][i]=1;
	while(k){
		if(k%2)ans=mul(ans,a);
		k/=2;a=mul(a,a);
	}
	return ans;
}
int main(){
	while(scanf("%lld",&n)!=EOF&&n){
		if(n<4){
			printf("0\n");
			continue;
		}
		jz a,b;
		a.to_0();b.to_0();
		a.a_cs();b.b_cs();
		a=mul(a,ksm(b,n-4));
       
		printf("%lld\n",a.z[1][1]%mod);
    }
}