#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 #define si(x) int(x.size()) #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< void dmpr(ostream&os,const T&t,const Args&... args){ os< ostream& operator<<(ostream&os,const array&a){ return os<(all(a)); } template void print_tuple(ostream&,const T&){ } template void print_tuple(ostream&os,const T&t){ if(i)os<<","; os<(t); print_tuple(os,t); } template ostream& operator<<(ostream&os,const tuple&t){ os<<"{"; print_tuple<0,tuple,Args...>(os,t); return os<<"}"; } template void print(t x,int suc=1){ cout<>i; return i; } vi readvi(int n,int off=0){ vi v(n); rep(i,n)v[i]=read()+off; return v; } template void print(const vector&v,int suc=1){ rep(i,v.size()) print(v[i],i==int(v.size())-1?suc:2); } string readString(){ string s; cin>>s; return s; } template T sq(const T& t){ return t*t; } //#define CAPITAL void yes(bool ex=true){ #ifdef CAPITAL cout<<"YES"<<"\n"; #else cout<<"Yes"<<"\n"; #endif if(ex)exit(0); } void no(bool ex=true){ #ifdef CAPITAL cout<<"NO"<<"\n"; #else cout<<"No"<<"\n"; #endif if(ex)exit(0); } void possible(bool ex=true){ #ifdef CAPITAL cout<<"POSSIBLE"<<"\n"; #else cout<<"Possible"<<"\n"; #endif if(ex)exit(0); } void impossible(bool ex=true){ #ifdef CAPITAL cout<<"IMPOSSIBLE"<<"\n"; #else cout<<"Impossible"<<"\n"; #endif if(ex)exit(0); } constexpr ll ten(int n){ return n==0?1:ten(n-1)*10; } const ll infLL=LLONG_MAX/3; #ifdef int const int inf=infLL; #else const int inf=INT_MAX/2-100; #endif int topbit(signed t){ return t==0?-1:31-__builtin_clz(t); } int topbit(ll t){ return t==0?-1:63-__builtin_clzll(t); } int botbit(signed a){ return a==0?32:__builtin_ctz(a); } int botbit(ll a){ return a==0?64:__builtin_ctzll(a); } int popcount(signed t){ return __builtin_popcount(t); } int popcount(ll t){ return __builtin_popcountll(t); } bool ispow2(int i){ return i&&(i&-i)==i; } ll mask(int i){ return (ll(1)< void mkuni(vc&v){ sort(all(v)); v.erase(unique(all(v)),v.ed); } ll rand_int(ll l, ll r) { //[l, r] #ifdef LOCAL static mt19937_64 gen; #else static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count()); #endif return uniform_int_distribution(l, r)(gen); } template void myshuffle(vc&a){ rep(i,si(a))swap(a[i],a[rand_int(0,i)]); } template int lwb(const vc&v,const t&a){ return lower_bound(all(v),a)-v.bg; } using uint=unsigned; using ull=unsigned long long; struct modinfo{uint mod,root;}; template struct modular{ static constexpr uint const &mod=ref.mod; static modular root(){return modular(ref.root);} uint v; //modular(initializer_listls):v(*ls.bg){} modular(ll vv=0){s(vv%mod+mod);} modular& s(uint vv){ v=vv>=1; } return res; } modular inv()const{return pow(mod-2);} /*modular inv()const{ int x,y; int g=extgcd(v,mod,x,y); assert(g==1); if(x<0)x+=mod; return modular(x); }*/ friend modular operator+(int x,const modular&y){ return modular(x)+y; } friend modular operator-(int x,const modular&y){ return modular(x)-y; } friend modular operator*(int x,const modular&y){ return modular(x)*y; } friend modular operator/(int x,const modular&y){ return modular(x)/y; } friend ostream& operator<<(ostream&os,const modular&m){ return os<>(istream&is,modular&m){ ll x;is>>x; m=modular(x); return is; } bool operator<(const modular&r)const{return v void inplace_fmt(const int n,mint*const f,bool inv){ static constexpr uint mod=mint::mod; static constexpr uint mod2=mod*2; static const int L=30; static mint g[L],ig[L],p2[L]; if(g[0].v==0){ rep(i,L){ mint w=-mint::root().pow(((mod-1)>>(i+2))*3); g[i]=w; ig[i]=w.inv(); p2[i]=mint(1<>=1){//input:[0,mod) rep(i,b){ uint x=f[i+b].v; f[i+b].v=f[i].v+mod-x; f[i].v+=x; } } if(b>>=1){//input:[0,mod*2) mint p=1; for(int i=0,k=0;i>=1){//input:[0,mod*3) mint p=1; for(int i=0,k=0;i>=1){//input:[0,mod*4) mint p=1; for(int i=0,k=0;i void inplace_fmt(vector&f,bool inv){ inplace_fmt(si(f),f.data(),inv); } template void half_fmt(const int n,mint*const f){ static constexpr uint mod=mint::mod; static constexpr uint mod2=mod*2; static const int L=30; static mint g[L],h[L]; if(g[0].v==0){ rep(i,L){ g[i]=-mint::root().pow(((mod-1)>>(i+2))*3); h[i]=mint::root().pow((mod-1)>>(i+2)); } } int b=n; int lv=0; if(b>>=1){//input:[0,mod) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*2) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*3) mint p=h[lv++]; for(int i=0,k=0;i>=1){//input:[0,mod*4) mint p=h[lv++]; for(int i=0,k=0;i void half_fmt(vector&f){ half_fmt(si(f),f.data()); } template vc multiply(vc x,const vc&y,bool same=false){ int n=si(x)+si(y)-1; int s=1; while(s z(s); rep(i,si(y))z[i]=y[i]; inplace_fmt(z,false); rep(i,s)x[i]*=z[i]; }else{ rep(i,s)x[i]*=x[i]; } inplace_fmt(x,true);x.resize(n); return x; } //59501818244292734739283969-1=5.95*10^25 までの値を正しく計算 //最終的な列の大きさが 2^24 までなら動く //最終的な列の大きさが 2^20 以下のときは,下の 3 つの素数を使ったほうが速い(は?) //VERIFY: yosupo //Yukicoder No980 (same=true) namespace arbitrary_convolution{ //constexpr modinfo base0{167772161,3};//2^25 * 5 + 1 //constexpr modinfo base1{469762049,3};//2^26 * 7 + 1 //constexpr modinfo base2{754974721,11};//2^24 * 45 + 1 constexpr modinfo base0{1045430273,3};//2^20 * 997 + 1 constexpr modinfo base1{1051721729,6};//2^20 * 1003 + 1 constexpr modinfo base2{1053818881,7};//2^20 * 1005 + 1 using mint0=modular; using mint1=modular; using mint2=modular; template vc sub(const vc&x,const vc&y,bool same=false){ int n=si(x)+si(y)-1; int s=1; while(s z(s);rep(i,si(x))z[i]=x[i].v; inplace_fmt(z,false); if(!same){ vc w(s);rep(i,si(y))w[i]=y[i].v; inplace_fmt(w,false); rep(i,s)z[i]*=w[i]; }else{ rep(i,s)z[i]*=z[i]; } inplace_fmt(z,true);z.resize(n); return z; } template vc multiply(const vc&x,const vc&y,bool same=false){ auto d0=sub(x,y,same); auto d1=sub(x,y,same); auto d2=sub(x,y,same); int n=si(d0); vc res(n); static const mint1 r01=mint1(mint0::mod).inv(); static const mint2 r02=mint2(mint0::mod).inv(); static const mint2 r12=mint2(mint1::mod).inv(); static const mint2 r02r12=r02*r12; static const mint w1=mint(mint0::mod); static const mint w2=w1*mint(mint1::mod); rep(i,n){ ull a=d0[i].v; ull b=(d1[i].v+mint1::mod-a)*r01.v%mint1::mod; ull c=((d2[i].v+mint2::mod-a)*r02r12.v+(mint2::mod-b)*r12.v)%mint2::mod; res[i].v=(a+b*w1.v+c*w2.v)%mint::mod; } return res; } } //using arbitrary_convolution::multiply; extern constexpr modinfo base{998244353,3}; //extern constexpr modinfo base{1000000007,0}; //modinfo base{1,0}; using mint=modular; const int vmax=(1<<21)+10; mint fact[vmax],finv[vmax],invs[vmax]; void initfact(){ fact[0]=1; rng(i,1,vmax){ fact[i]=fact[i-1]*i; } finv[vmax-1]=fact[vmax-1].inv(); for(int i=vmax-2;i>=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); } mint sub(int n,int a){ return (fact[n]-fact[a]*fact[n-a]); } void waf(vi&x,int a){ int n=si(x); while(1){ int i=-1,j=-1; rep(k,n)if(x[k]>a){ i=k; break; } per(k,n)if(x[k]<=a){ j=k; break; } if(i>n>>a>>b; //int bans=brute(n,a,b); //cerr<b)swap(a,b); if(a==b){ print(fact[n]*n); return 0; } mint ans; ans+=sq(a)*fact[n-1]; ans+=sq(b-a)*fact[n-1]; ans+=sq(n-b)*fact[n-1]; /*{ int cnt=0; vi p(n);iota(all(p),0); do{ int mn=*min_element(p.bg+a,p.bg+b); int mx=*max_element(p.bg+a,p.bg+b); int x=0,y=0; rep(i,a)if(p[i]mx)y++; cnt+=min(x,y); }while(next_permutation(all(p))); ans+=cnt*2; }*/ mint cnt; { vc x(a),y(n-b); rep(i,si(x))x[i]=choose(a,i+1)*(i+1); rep(i,si(y))y[i]=choose(n-b,i+1)*(i+1); auto z=multiply(x,y); rep(i,si(z)){ cnt+=z[i]*fact[n-(i+2)]*fact[i]; } } ans+=cnt*2; print(ans); }