// https://judge.yosupo.jp/submission/958 #include using namespace std; using ll=long long; #define int ll #define rng(i,a,b) for(int i=int(a);i=int(a);i--) #define per(i,b) gnr(i,0,b) #define pb push_back #define eb emplace_back #define a first #define b second #define bg begin() #define ed end() #define all(x) x.bg,x.ed #ifdef LOCAL #define dmp(x) cerr<<__LINE__<<" "<<#x<<" "< void chmax(t&a,u b){if(a void chmin(t&a,u b){if(b using vc=vector; template using vvc=vc>; using pi=pair; using vi=vc; template ostream& operator<<(ostream& os,const pair& p){ return os<<"{"< ostream& operator<<(ostream& os,const vc& v){ os<<"{"; for(auto e:v)os<>=1; } return res; } mint inv()const{return pow(mod-2);} /*mint inv()const{ int x,y; int g=extgcd(v,mod,x,y); assert(g==1); if(x<0)x+=mod; return mint(x); }*/ friend ostream& operator<<(ostream&os,const mint&m){ return os<=0;i--){ finv[i]=finv[i+1]*(i+1); } for(int i=vmax-1;i>=1;i--){ invs[i]=finv[i]*fact[i-1]; } } mint choose(int n,int k){ return fact[n]*finv[n-k]*finv[k]; } mint binom(int a,int b){ return fact[a+b]*finv[a]*finv[b]; } mint catalan(int n){ return binom(n,n)-(n-1>=0?binom(n-1,n+1):0); } #define USE_FMT //998244353 const mint prim_root=3; /* //in-place fft //size of input must be a power of 2 void inplace_fmt(vector&f,const bool inv){ const int n=f.size(); const mint root=inv?prim_root.inv():prim_root; vc g(n); for(int b=n/2;b>=1;b/=2){ mint w=root.pow((mint::base-1)/(n/b)),p=1; for(int i=0;i&f){ const int n=f.size(); for(int b=n/2;b>=1;b/=2){ for(int i=0;i&f){ const int n=f.size(); for(int b=1;b<=n/2;b*=2){ for(int i=0;i&f,const bool i){ if(!i)broken_fmt(f); else broken_ifmt(f); } vc multiply(vc x,vc y,bool same=false){ int n=x.size()+y.size()-1; int s=1; while(s struct Poly:public vc{ template Poly(Args...args):vc(args...){} Poly(initializer_listinit):vc(all(init)){} int size()const{ return vc::size(); } void ups(int s){ if(size()resize(s,0); } Poly low(int s)const{ return Poly(this->bg,this->bg+min(max(s,int(1)),size())); } Poly rev()const{ auto r=*this; reverse(all(r)); return r; } Poly& operator+=(const Poly&r){ ups(r.size()); rep(i,r.size()) (*this)[i]+=r[i]; return *this; } Poly& operator-=(const Poly&r){ ups(r.size()); rep(i,r.size()) (*this)[i]-=r[i]; return *this; } template Poly& operator*=(T t){ for(auto&v:*this) v*=t; return *this; } Poly& operator*=(const Poly&r){ return *this=multiply(*this,r); } Poly square()const{ return multiply(*this,*this,true); } #ifndef USE_FMT Poly inv(int s)const{ Poly r{D(1)/(*this)[0]}; for(int n=1;n f=low(2*n); f.resize(n*4); inplace_fmt(f,false); rep(i,n*4) r[i]=r[i]*2-r[i]*r[i]*f[i]; inplace_fmt(r,true); r.resize(2*n); } return r.low(s); } #endif template Poly& operator/=(T t){ return *this*=D(1)/D(t); } Poly quotient(const Poly&r,const Poly&rri)const{ int m=r.size(); assert(r[m-1].v); int n=size(); int s=n-m+1; if(s<=0) return {0}; return (rev().low(s)*rri.low(s)).low(s).rev(); } Poly& operator/=(const Poly&r){ return *this=quotient(r,r.rev().inv(max(size()-r.size(),int(0))+1)); } Poly& operator%=(const Poly&r){ *this-=*this/r*r; return *this=low(r.size()-1); } Poly operator+(const Poly&r)const{return Poly(*this)+=r;} Poly operator-(const Poly&r)const{return Poly(*this)-=r;} template Poly operator*(T t)const{return Poly(*this)*=t;} Poly operator*(const Poly&r)const{return Poly(*this)*=r;} template Poly operator/(T t)const{return Poly(*this)/=t;} Poly operator/(const Poly&r)const{return Poly(*this)/=r;} Poly operator%(const Poly&r)const{return Poly(*this)%=r;} Poly dif()const{ Poly r(max(int(0),size()-1)); rep(i,r.size()) r[i]=(*this)[i+1]*(i+1); return r; } Poly inte()const{ Poly r(size()+1,0); rep(i,size()) r[i+1]=(*this)[i]*invs[i+1]; return r; } //opencupXvcIII GP of Peterhof H Poly log(int s)const{ return (low(s).dif()*inv(s-1)).low(s-1).inte(); } //Petrozavodsk 2019w Day1 G //yosupo judge Poly exp(int s)const{ return exp2(s).a; } //2つほしいときはコメントアウトの位置ずらす pair exp2(int s)const{ assert((*this)[0]==mint(0)); Poly f{1},g{1}; for(int n=1;;n*=2){ if(n>=s)break; g=g*2-(g.square()*f).low(n); //if(n>=s)break; Poly q=low(n).dif(); q=q+g*(f.dif()-f*q).low(2*n-1); f=f+(f*(low(2*n)-q.inte())).low(2*n); } return make_pair(f.low(s),g.low(s)); } //CF250 E Poly sqrt(int s)const{ assert((*this)[0]==1); Poly r{1}; for(int n=1;n divide(const Poly&r,const Poly&rri)const{ Poly a=quotient(r,rri); Poly b=*this-a*r; return make_pair(a,b.low(r.size()-1)); } //Yukicoder No.215 Poly pow_mod(int n,const Poly&r)const{ Poly rri=r.rev().inv(r.size()); Poly cur{1},x=*this%r; while(n){ if(n%2) cur=(cur*x).divide(r,rri).b; x=(x*x).divide(r,rri).b; n/=2; } return cur; } D eval(D x)const{ D r=0,w=1; for(auto v:*this){ r+=w*v; w*=x; } return r; } }; /* signed main(){ cin.tie(0); ios::sync_with_stdio(0); cout<>n; n++; Poly f(n); rep(i,n) f[i]=finv[i+1]; auto g=f.inv(n); rep(i,n) cout< g(N + 1), q(N + 1); for (int i = 0; i <= N; ++i) { g[i] = fact[i + 1] + 1; q[i] = fact[i + 1]; } g[0] = 1; const auto h = g * q.inv(N + 1); const mint ans = mint(1) - h[N]; printf("%u\n", ans.v); } return 0; }