#include #include using namespace std; template struct Number_Theoretic_Transform { static vectordw,dw_inv; static int log; static mint root; static void ntt(vector& f) { init(); const int n=f.size(); for(int m=n;m>>=1;) { mint w=1; for(int s=0,k=0;s& f, bool flag=true) { init(); const int n=f.size(); for(int m=1;m>=1; log++; } dw.resize(log); dw_inv.resize(log); for(int i=0;i>(i+2)); dw_inv[i]=dw[i].inv(); } } }; template vectorNumber_Theoretic_Transform::dw=vector(); template vectorNumber_Theoretic_Transform::dw_inv=vector(); template int Number_Theoretic_Transform::log=0; template mint Number_Theoretic_Transform::root=mint(3); template struct Formal_Power_Series:vector { using FPS=Formal_Power_Series; using vector::vector; using NTT=Number_Theoretic_Transform; void ntt(){NTT::ntt(*this);} void intt(bool flag=true){NTT::intt(*this,flag);} FPS &operator+=(const mint& r) { if(this->empty())this->resize(1); (*this)[0]+=r; return *this; } FPS &operator-=(const mint& r) { if(this->empty())this->resize(1); (*this)[0]-=r; return *this; } FPS &operator*=(const mint& r) { for(mint &x:*this)x*=r; return *this; } FPS &operator/=(const mint& r) { mint invr=r.inv(); for(mint &x:*this)x*=invr; return *this; } FPS operator+(const mint& r)const{return FPS(*this)+=r;} FPS operator-(const mint& r)const{return FPS(*this)-=r;} FPS operator*(const mint& r)const{return FPS(*this)*=r;} FPS operator/(const mint& r)const{return FPS(*this)/=r;} FPS& operator+=(const FPS& f) { if(this->size()resize(f.size()); for(int i=0;i<(int)f.size();i++)(*this)[i]+=f[i]; return *this; } FPS& operator-=(const FPS& f) { if(this->size()resize(f.size()); for(int i=0;i<(int)f.size();i++)(*this)[i]-=f[i]; return *this; } FPS& operator*=(const FPS& f) { *this=convolution(*this,f); return *this; } FPS& operator/=(const FPS& f) { return *this*=f.inv(); } FPS& operator%=(const FPS& f) { *this-=this->div(f)*f; this->shrink(); return *this; } FPS operator+(const FPS& f)const{return FPS(*this)+=f;} FPS operator-(const FPS& f)const{return FPS(*this)-=f;} FPS operator*(const FPS& f)const{return FPS(*this)*=f;} FPS operator/(const FPS& f)const{return FPS(*this)/=f;} FPS operator%(const FPS& f)const{return FPS(*this)%=f;} FPS operator-()const { FPS res(this->size()); for(int i=0;i<(int)this->size();i++)res[i]-=(*this)[i]; return res; } FPS div(FPS f) { if(this->size()size()-f.size()+1; return (rev().pre(n)*f.rev().inv(n)).pre(n).rev(n); } FPS pre(int deg)const { return FPS(begin(*this),begin(*this)+min((int)this->size(),deg)); } FPS rev(int deg=-1)const { FPS res(*this); if(deg!=-1)res.resize(deg,0); reverse(begin(res),end(res)); return res; } void shrink() { while(!this->empty()&&this->back()==0)this->pop_back(); } FPS dot(FPS f)const { int n=min(this->size(),f.size()); FPS res(n); for(int i=0;i>(int deg)const { if((int)this->size()<=deg)return{}; FPS res(*this); res.erase(res.begin(),res.begin()+deg); return res; } FPS& operator>>=(int deg) { return *this=*this>>(deg); } mint operator()(const mint& r) { mint res=0,powr=1; for(auto x:*this) { res+=x*powr; powr*=r; } return res; } FPS diff()const { int n=this->size(); FPS res(max(0,n-1)); for(int i=1;isize(); FPS res(n+1); res[0]=0; for(int i=0;isize(); if(deg==-1)deg=n; FPS res(deg); res[0]={(*this)[0].inv()}; for(int d=1;dsize(); vectorinv; inv.reserve(deg+1); inv.push_back(mint::raw(0)); inv.push_back(mint::raw(1)); auto inplace_integral=[&](FPS& f)->void { int n=f.size(); long long mod=mint::mod(); while(inv.size()<=f.size()) { int i=inv.size(); inv.push_back((-inv[mod%i])*(mod/i)); } f.insert(begin(f),mint::raw(0)); for(int i=1;i<=n;i++)f[i]*=inv[i]; }; auto inplace_diff=[](FPS& f)->void { if(f.empty())return; f.erase(begin(f)); mint cef=1; for(int i=0;i<(int)f.size();i++) { f[i]*=cef; cef++; } }; FPS b={1,1size()?(*this)[1]:0}; FPS c={1},z1,z2={1,1}; for(int m=2;msize()),m)); inplace_diff(x); x.push_back(mint::raw(0)); x.ntt(); x=x.dot(y); x.intt(); x-=b.diff(); x.resize(2*m); for(int i=0;isize()),2*m);i++)x[i]+=(*this)[i]; fill(begin(x),begin(x)+m,mint::raw(0)); x.ntt(); x=x.dot(y); x.intt(); b.insert(end(b),begin(x)+m,end(x)); } return FPS{begin(b),begin(b)+deg}; } FPS log(int deg=-1)const { assert((*this)[0]==1); int n=this->size(); if(deg==-1)deg=n; return (this->diff()*this->inv()).pre(deg-1).integral(); } FPS pow(long long k, int deg=-1)const { if(deg==-1)deg=this->size(); if(k==0) { FPS res(deg); res[0]=mint::raw(1); return res; } FPS res=*this; int cnt0=0; while(cnt0(deg-1)/k) { FPS res(deg); return res; } res=res>>cnt0; deg-=cnt0*k; res=((res/res[0]).log(deg)*k).exp(deg)*res[0].pow(k); res=res<<(cnt0*k); return res.pre(deg); } FPS taylor_shift(mint c) { int n=this->size(); FPS fact(n),fact_inv(n); { // calc fact and fact inv fact[0]=1; for(int i=1;i=1;i--)fact_inv[i-1]=i*fact_inv[i]; } FPS res(*this); res=res.dot(fact); res=res.rev(); FPS bs(n,mint::raw(1)); for(int i=1;imultipoint_evaluation(vector&x) { if(x.empty())return{}; int m=x.size(),n=1; if(this->size()==0){return vector(m,0);} if(this->size()==1){return vector(m,(*this)[0]);} while(m>n)n<<=1; vectorf(n<<1,FPS({mint(1)})); for(int i=0;i0;i--)f[i]=f[i<<1]*f[(i<<1)|1]; f[1]=(*this)%f[1]; for(int i=2;i>1]%f[i]; vectorres(m); for(int i=0;i; FPS subset_sum(int N, vector&A, bool neg=false) { const int mod=mint::mod(); vectorcnt(N+1,0); for(int a:A)cnt[a]++; vectorinv(N+1); inv[1]=1; for(int i=2;i<=N;i++)inv[i]=-inv[mod%i]*(mod/i); FPS f(N+1); for(int i=1;i<=N;i++)for(int j=1;i*j<=N;j++) { if(j&1&&!neg)f[i*j]+=cnt[i]*inv[j]; else f[i*j]-=cnt[i]*inv[j]; } return f.exp(); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N,K; cin>>N>>K; vectorA,B; for(int i=1;i<=N;i++) { if((long)(K+1)*i<=N)A.push_back(i*(K+1)); B.push_back(i); } auto f=subset_sum(N+1,A,1); auto g=subset_sum(N+1,B,1); f/=g; for(int i=1;i<=N;i++)cout<