#include #include #include using namespace std; using namespace atcoder; int get_primitive_root(int mod) { if (mod==167772161)return 3; if (mod==469762049)return 3; if (mod==754974721)return 11; if (mod==998244353)return 3; if (mod==1224736769)return 3; assert(0); return 0; } template void bit_rev(vector&a) { int n=a.size(); for(int i=0,j=1;j>1;k>(i^=k);k>>=1); if(i void NTT(vector&f, bool ordered=false) { constexpr int mod=mint::mod(); mint primitive_root=get_primitive_root(mod); int n=f.size(); for(int m=n;m>1;m>>=1) { mint omega=primitive_root.pow((mod-1)/m); for(int s=0;s void INTT(vector&f, bool ordered=false) { constexpr int mod=mint::mod(); mint primitive_root=get_primitive_root(mod); if(ordered)bit_rev(f); int n=f.size(); for(int m=2;m<=n;m<<=1) { mint omega=primitive_root.pow((mod-1)/m).inv(); for(int s=0;s struct FormalPowerSeries:vector { using FPS=FormalPowerSeries; using vector::vector; using vector::operator=; 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 r_=r.inv(); for(mint &x:*this)x*=r_; 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&r) { if(this->size()resize(r.size()); for(int i=0;i<(int)r.size();i++)(*this)[i]+=r[i]; return *this; } FPS operator-=(const FPS&r) { if(this->size()resize(r.size()); for(int i=0;i<(int)r.size();i++)(*this)[i]-=r[i]; return *this; } FPS operator*=(const FPS&r) { *this=convolution(*this,r); return *this; } FPS operator/=(const FPS&r) { *this*=r.inv(); return *this; } FPS operator%=(const FPS&r) { *this-=*this/r*r; shrink(); return *this; } FPS operator+(const FPS&r)const{return FPS(*this)+=r;} FPS operator-(const FPS&r)const{return FPS(*this)-=r;} FPS operator*(const FPS&r)const{return FPS(*this)*=r;} FPS operator/(const FPS&r)const{return FPS(*this)/=r;} FPS operator%(const FPS&r)const{return FPS(*this)%=r;} FPS pre(int n)const { return FPS(this->begin(),this->begin()+min((int)this->size(),n)); } FPS rev(int n=-1)const { FPS res=*this; if(n!=-1)res.resize(n,0); return FPS(res.rbegin(),res.rend()); } void shrink() { while(!this->empty()&&this->back()==0)this->pop_back(); } FPS operator<<(int n)const { FPS res=*this; res.insert(res.begin(),n,0); return res; } FPS operator>>(int n)const { if((int)this->size()<=n)return{}; FPS res=*this; res.erase(res.begin(),res.begin()+n); return res; } mint operator()(const mint&r) { mint r_=0,powr=1; for(int i=0;isize();i++) { for(auto x:*this) { r_+=x*powr; powr*=r; } return r_; } } FPS inv(int n=-1)const { assert(!this->empty()); assert((*this)[0]!=0); if(n==-1)n=this->size(); FPS res={(*this)[0].inv()}; for(int d=1;df=pre(2*d); vectorg=res; f.resize(2*d); g.resize(2*d); NTT(f); NTT(g); for(int i=0;i<2*d;i++)f[i]*=g[i]; INTT(f); for(int i=0;isize(); FPS res={1}; for(int i=1;ipre(i<<1)+mint(1)-res.log(i<<1))).pre(i<<1); } return res; } FPS log(int n=-1)const { assert((*this)[0]==1); if(n==-1)n=this->size(); return FPS((diff()*inv(n)).pre(n-1)).integral(); } FPS pow(long long k, int n=-1)const { if(n==-1)n=this->size(); if(k==0) { FPS res(n); res[0]=1; return res; } FPS res=*this; int cnt0=0; while(cnt0(n-1)/k) { FPS res(n); return res; } res=res>>cnt0; n-=cnt0*k; res=((res/res[0]).log(n)*k).exp(n)*res[0].pow(k); res=res<<(cnt0*k); return res; } FPS diff()const { int n=this->size(); FPS res(max(0,n-1)); for(int i=1;i<=(int)res.size();i++) { res[i-1]=(*this)[i]*i; } return res; } FPS integral()const { FPS res(this->size()+1); res[0]=0; for(int i=0;i<(int)res.size()-1;i++) { res[i+1]=(*this)[i]/(i+1); } return res; } vectormultipoint_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; int N; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>N; FPS f(2*N); mint fact=1; for(int i=1;i<=N;i++) { f[i]=i*fact.inv(); fact*=i; } f=f.pow(N); mint ans=f[2*N-2]; mint invN=mint(N).inv(); for(int i=1;i<=N-2;i++) { ans*=i; ans*=invN; } cout << ans.val() << endl; }