// #pragma GCC target("avx,avx2") // #pragma GCC optimize("Ofast") #include using namespace std; using ll = long long; using uint = unsigned int; using ull = unsigned long long; #define rep(i,n) for(int i=0;i=0;i--) #define per1(i,n) for(int i=int(n);i>0;i--) #define all(c) c.begin(),c.end() #define si(x) int(x.size()) #define pb push_back #define eb emplace_back #define fs first #define sc second template using V = vector; template using VV = vector>; template bool chmax(T& x, U y){ if(x bool chmin(T& x, U y){ if(y void mkuni(V& v){sort(all(v));v.erase(unique(all(v)),v.end());} template int lwb(const V& v, const T& a){return lower_bound(all(v),a) - v.begin();} template V Vec(size_t a) { return V(a); } template auto Vec(size_t a, Ts... ts) { return V(ts...))>(a, Vec(ts...)); } template ostream& operator<<(ostream& o,const pair &p){ return o<<"("< ostream& operator<<(ostream& o,const vector &vc){ o<<"{"; for(const T& v:vc) o< D divFloor(D a, D b){ return a / b - (((a ^ b) < 0 && a % b != 0) ? 1 : 0); } template D divCeil(D a, D b) { return a / b + (((a ^ b) > 0 && a % b != 0) ? 1 : 0); } template T rnd(T l,T r){ //[l,r) using D = uniform_int_distribution; static random_device rd; static mt19937 gen(rd()); return D(l,r-1)(gen); } template T rnd(T n){ //[0,n) return rnd(T(0),n); } template struct ModInt{ using uint = unsigned int; using ll = long long; using ull = unsigned long long; constexpr static uint mod = mod_; uint v; ModInt():v(0){} ModInt(ll _v):v(normS(_v%mod+mod)){} explicit operator bool() const {return v!=0;} static uint normS(const uint &x){return (x [0 , mod-1] static ModInt make(const uint &x){ModInt m; m.v=x; return m;} ModInt operator+(const ModInt& b) const { return make(normS(v+b.v));} ModInt operator-(const ModInt& b) const { return make(normS(v+mod-b.v));} ModInt operator-() const { return make(normS(mod-v)); } ModInt operator*(const ModInt& b) const { return make((ull)v*b.v%mod);} ModInt operator/(const ModInt& b) const { return *this*b.inv();} ModInt& operator+=(const ModInt& b){ return *this=*this+b;} ModInt& operator-=(const ModInt& b){ return *this=*this-b;} ModInt& operator*=(const ModInt& b){ return *this=*this*b;} ModInt& operator/=(const ModInt& b){ return *this=*this/b;} ModInt& operator++(int){ return *this=*this+1;} ModInt& operator--(int){ return *this=*this-1;} template friend ModInt operator+(T a, const ModInt& b){ return (ModInt(a) += b);} template friend ModInt operator-(T a, const ModInt& b){ return (ModInt(a) -= b);} template friend ModInt operator*(T a, const ModInt& b){ return (ModInt(a) *= b);} template friend ModInt operator/(T a, const ModInt& b){ return (ModInt(a) /= b);} ModInt pow(ll p) const { if(p<0) return inv().pow(-p); ModInt a = 1; ModInt x = *this; while(p){ if(p&1) a *= x; x *= x; p >>= 1; } return a; } ModInt inv() const { // should be prime return pow(mod-2); } // ll extgcd(ll a,ll b,ll &x,ll &y) const{ // ll p[]={a,1,0},q[]={b,0,1}; // while(*q){ // ll t=*p/ *q; // rep(i,3) swap(p[i]-=t*q[i],q[i]); // } // if(p[0]<0) rep(i,3) p[i]=-p[i]; // x=p[1],y=p[2]; // return p[0]; // } // ModInt inv() const { // ll x,y; // extgcd(v,mod,x,y); // return make(normS(x+mod)); // } bool operator==(const ModInt& b) const { return v==b.v;} bool operator!=(const ModInt& b) const { return v!=b.v;} bool operator<(const ModInt& b) const { return v>(istream &o,ModInt& x){ ll tmp; o>>tmp; x=ModInt(tmp); return o; } friend ostream& operator<<(ostream &o,const ModInt& x){ return o<; //using mint = ModInt<1000000007>; V fact,ifact,invs; mint Choose(int a,int b){ if(b<0 || a=0;i--) ifact[i] = ifact[i+1] * (i+1); rep1(i,N-1) invs[i] = fact[i-1] * ifact[i]; } V brute(int N, int K){ V res(N+1); V pK(N+1); rep(i,N+1) pK[i] = mint(i).pow(K); rep1(a,N) rep1(b,min(a,N-a)) rep1(c,min(b,N-a-b)){ mint hook = mint(b-c+1)*(a-b+1)*(a-c+2) * ifact[c]*ifact[b+1]*ifact[a+2]; res[a+b+c] += pK[a] * hook*hook; } rep1(i,N) res[i] *= fact[i]*fact[i]; return res; } V solve(int N, int K){ /* a' = a+2, b' = b+1, c' = c for a'>b'>c'>0: res[a'+b'+c'-3] += (a'-2)^K * ( (b'-c')(a'-b')(a'-c')/a'!b'!c'! )^2 */ V res(N+1); V pK(N+5); rep(i,N+5) pK[i] = mint(i).pow(K); VV ai(5,V(N+5)); for(int a=3;a<=N+2;a++){ mint a4 = mint(a)*a*a*a, a3 = mint(a)*a*a, a2 = mint(a)*a; for(int bc=3;bc<=min(N+3-a,a+a-3);bc++){ ll b = a-1, c = bc-b; if(b > c && c > 0){ shows("add: ",a,b,c); mint com = ifact[b]*ifact[b]*ifact[c]*ifact[c]*(b-c)*(b-c); ai[4][bc] += com; ai[3][bc] += com * (-b-b-c-c); ai[2][bc] += com * (b*b+4*b*c+c*c); ai[1][bc] += com * (-2*b*c*(b+c)); ai[0][bc] += com * (b*b*c*c); } mint com = pK[a-2] * ifact[a]*ifact[a]; mint tmp = ai[4][bc]*a4 + ai[3][bc]*a3 + ai[2][bc]*a2 + ai[1][bc]*a + ai[0][bc]; res[a+bc-3] += com * tmp; } } rep1(i,N) res[i] *= fact[i]*fact[i]; return res; } void TEST(){ int N; cin >> N; cout << si(solve(N,TEN(9))) << endl; exit(0); } int main(){ cin.tie(0); ios::sync_with_stdio(false); //DON'T USE scanf/printf/puts !! cout << fixed << setprecision(20); InitFact(100000); // TEST(); int N = 30000; int K; cin >> K; auto f = solve(N,K); cout << N << endl; rep1(i,N) cout << f[i] << (i==N ? '\n' : ' '); }