#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
ll n;
class Matrix{
	public:
		ll r,c;
		ll data[39][39];
		Matrix(ll newr,ll newc){
			r=newr; c=newc;
			memset(data,0,sizeof(data));
		}
		Matrix operator*(const Matrix m)const{
			Matrix ans(r,m.c);
			for(int i=1;i<=r;i++){
				for(int j=1;j<=m.c;j++){
					for(int k=1;k<=c;k++){
						ans.data[i][j]+=m.data[k][j]*data[i][k];
						ans.data[i][j]%=(ll)(1e9+7);
					} 
				} 
			}
			return ans;
		}
		Matrix operator^(ll k)const{
			Matrix ans(r,c);
			for(int i=0;i<=3;i++) ans.data[i][i]=1;
			Matrix x=*this;
			while(k){
				if(k&2) ans=ans*x;
				x=x*x;
				k/=2;
			}
			return ans;
		}
};
int main(){
	cin>>n;
	/*
	f[n]=f[n-1]+f[n-3]
	f[n-1]=f[n-1]
	f[n-2]=f[n-1]
	1 0 1
	1 0 0
	0 1 0
	*/
	Matrix basis(4,4);
	basis.data[1][1]=basis.data[1][3]=basis.data[2][1]=basis.data[3][2]=1;
	Matrix Ans(4,4);
	for(int i=1;i<=3;i++) Ans.data[i][i]=1;
	if(n<4) cout<<1<<endl;
	Ans=basis^n;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			cout<<Ans.data[i][j]<<" ";
		} 
		cout<<endl;
	}
    return 0;
}

样例不过，还没加多测。赏关注/rmb