#include using namespace std; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a struct Mint{ static constexpr T mod = MOD; T v; Mint():v(0){} Mint(signed v):v(v){} Mint(long long t){v=t%MOD;if(v<0) v+=MOD;} Mint pow(long long k){ Mint res(1),tmp(v); while(k){ if(k&1) res*=tmp; tmp*=tmp; k>>=1; } return res; } static Mint add_identity(){return Mint(0);} static Mint mul_identity(){return Mint(1);} Mint inv(){return pow(MOD-2);} Mint& operator+=(Mint a){v+=a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator-=(Mint a){v+=MOD-a.v;if(v>=MOD)v-=MOD;return *this;} Mint& operator*=(Mint a){v=1LL*v*a.v%MOD;return *this;} Mint& operator/=(Mint a){return (*this)*=a.inv();} Mint operator+(Mint a) const{return Mint(v)+=a;} Mint operator-(Mint a) const{return Mint(v)-=a;} Mint operator*(Mint a) const{return Mint(v)*=a;} Mint operator/(Mint a) const{return Mint(v)/=a;} Mint operator-() const{return v?Mint(MOD-v):Mint(v);} bool operator==(const Mint a)const{return v==a.v;} bool operator!=(const Mint a)const{return v!=a.v;} bool operator <(const Mint a)const{return v constexpr T Mint::mod; template ostream& operator<<(ostream &os,Mint m){os< class Enumeration{ using M = M_; protected: static vector fact,finv,invs; public: static void init(int n){ n=min(n,M::mod-1); int m=fact.size(); if(n=m;i--) finv[i-1]=finv[i]*M(i); for(int i=m;i<=n;i++) invs[i]=finv[i]*fact[i-1]; } static M Fact(int n){ init(n); return fact[n]; } static M Finv(int n){ init(n); return finv[n]; } static M Invs(int n){ init(n); return invs[n]; } static M C(int n,int k){ if(n vector Enumeration::fact=vector(); template vector Enumeration::finv=vector(); template vector Enumeration::invs=vector(); //INSERT ABOVE HERE using M = Mint; const int MAX = 1e5; M dp[6][MAX]={}; M nx[6][MAX]={}; signed main(){ cin.tie(0); ios::sync_with_stdio(0); using E = Enumeration; E::init(1e6); int n; cin>>n; if(n>5000) abort(); dp[3][1]=M(1); dp[4][1]=M(2); dp[5][1]=M(1); vector ans(n+n+1,0); for(int i=1;i<=n+n;i++){ for(int j=1;j<=i;j++){ int k=i-j; if(j%4==0 or j%4==1) ans[k]+=dp[2][j]*E::P(n,n-j); else ans[k]-=dp[2][j]*E::P(n,n-j); } for(int j=1;j<=i;j++){ nx[0][j]+=dp[0][j]; nx[1][j]+=dp[0][j]*M(2); nx[2][j]+=dp[0][j]; nx[1][j]+=dp[1][j]; nx[2][j]+=dp[1][j]; nx[2][j]+=dp[2][j]; nx[0][j]+=dp[3][j]; nx[1][j]+=dp[3][j]*M(2); nx[2][j]+=dp[3][j]; nx[1][j]+=dp[4][j]; nx[2][j]+=dp[4][j]; nx[2][j]+=dp[5][j]; nx[3][j+1]+=dp[2][j]; nx[4][j+1]+=dp[2][j]*M(2); nx[5][j+1]+=dp[2][j]; } for(int j=1;j<=i;j++) for(int t=0;t<6;t++) dp[t][j]=nx[t][j],nx[t][j]=0; } for(int i=1;i<=n;i++) cout<