#include using namespace std; using Int = long long; template inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template inline void chmax(T1 &a,T2 b){if(a T mod_pow(T a,long long n,T mod){ using ll = long long; T res(1); while(n){ if(n&1) res=(ll)res*a%mod; a=(ll)a*a%mod; n>>=1; } return res; } template map factorize(T x){ map res; for(Int i=2;i*i<=x;i++){ while(x%i==0){ x/=i; res[i]++; } } if(x!=1) res[x]++; return res; } template T order(T x,T MOD){ static map> dp; vector &ps=dp[MOD]; if(ps.empty()){ auto fs=factorize(MOD-1); for(auto p:fs) ps.emplace_back(p.first); } T res=MOD-1; for(T p:ps){ while(res%p==0){ if(mod_pow(x,res/p,MOD)!=1) break; res/=p; } } return res; } // find x s.t. a^x = b (x >= 0) template T mod_log(T a,T b,T mod){ using ll = long long; ll g=1; { ll m=mod; while(m){ g=(ll)g*a%mod; m>>=1; } } g=__gcd(g,(ll)mod); ll c=0,t=1; while(t%g){ if(t==b) return c; t=t*a%mod; c++; } // not found if(b%g) return mod; t/=g;b/=g; const ll n=mod/g; ll h=0,gs=1; while(h*h bs; { ll s=0,e=b; while(s 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< struct NTT{ static constexpr Int md = bmds(X); static constexpr Int rt = brts(X); using M = Mint; vector< vector > rts,rrts; void ensure_base(Int n){ if((Int)rts.size()>=n) return; rts.resize(n);rrts.resize(n); for(Int i=1;i &as,bool f,Int n=-1){ if(n==-1) n=as.size(); assert((n&(n-1))==0); ensure_base(n); for(Int i=0,j=1;j+1>1;k>(i^=k);k>>=1); if(i>j) swap(as[i],as[j]); } for(Int i=1;i multiply(vector as,vector bs){ Int need=as.size()+bs.size()-1; Int sz=1; while(sz multiply(vector as,vector bs){ vector am(as.size()),bm(bs.size()); for(Int i=0;i<(Int)am.size();i++) am[i]=M(as[i]); for(Int i=0;i<(Int)bm.size();i++) bm[i]=M(bs[i]); vector cm=multiply(am,bm); vector cs(cm.size()); for(Int i=0;i<(Int)cs.size();i++) cs[i]=cm[i].v; return cs; } }; template constexpr Int NTT::md; template constexpr Int NTT::rt; //INSERT ABOVE HERE signed main(){ Int P; cin>>P; vector as(P),bs(P); for(Int i=1;i>as[i]; for(Int i=1;i>bs[i]; random_device rd; mt19937 mt(rd()); uniform_int_distribution ud(1,P-1); Int rt=ud(mt); while(order(rt,P)!=P-1) rt=ud(mt); vector A(P),B(P); for(Int i=1;i ntt; using M = decltype(ntt)::M; auto C=ntt.multiply(A,B); vector cs(P); for(Int i=0;i<(Int)C.size();i++) cs[mod_pow(rt,i,P)]+=C[i]; for(Int i=1;i1) cout<<" "; cout<