modint
const int mod=998244353;
struct mint{
int x;
mint(int x=0):x(x){}
mint&operator+=(mint a){if((x+=a.x)>=mod)x-=mod;return *this;}
mint&operator-=(mint a){if((x-=a.x)<0)x+=mod;return *this;}
mint&operator*=(mint a){x=(ll)x*a.x%mod;return *this;}
friend mint operator+(mint a,mint b){return a+=b;}
friend mint operator-(mint a,mint b){return a-=b;}
friend mint operator*(mint a,mint b){return a*=b;}
mint pow(ll b=mod-2){
mint a=x,res=1;
for(;b;b>>=1,a*=a)if(b&1)res*=a;
return res;
}
};
vector<mint>fac,ifac,inv;
void initC(int n){
if(inv.empty())fac=ifac=inv=vector<mint>(2,1);
int m=inv.size(); ++n;
if(m>=n)return;
inv.resize(n),fac.resize(n),ifac.resize(n);
F(i,m,n-1){
inv[i]=inv[mod%i]*(mod-mod/i);
fac[i]=fac[i-1]*i,ifac[i]=ifac[i-1]*inv[i];
}
}
mint C(int n,int m){
if(n<m||m<0)return 0;
return initC(n),fac[n]*ifac[m]*ifac[n-m];
}
acam
int tr[N][26],tot,fail[N];
void ins(string s){
int u=0;
for(auto c:s){
int v=c-'a';
if(!tr[u][v]) tr[u][v]=++tot;
u=tr[u][v];
}
}
void bd(){
queue<int> q;
F(i,0,25) if(tr[0][i]) q.push(tr[0][i]);
while(q.size()){
int u=q.front();
q.pop();
F(i,0,25){
if(tr[u][i]){
fail[tr[u][i]]=tr[fail[u]][i];
q.push(tr[u][i]);
}else tr[u][i]=tr[fail[u]][i];
}
}
}
sa
char s[N];
int n,sa[N],rk[N],ht[N],mn[N][23];
void init(){
static int cnt[N],SA[N],RK[N],h[N];
F(i,1,n)++cnt[(int)s[i]];
F(i,1,255)cnt[i]+=cnt[i-1];
F(i,1,n)sa[cnt[(int)s[i]]--]=i;
F(i,1,n)rk[sa[i]]=rk[sa[i-1]]+(s[sa[i-1]]!=s[sa[i]]);
for(int p=1;p<=n;p*=2){
F(i,1,n)cnt[rk[sa[i]]]=i;
dF(i,n,1)if(sa[i]>p)SA[cnt[rk[sa[i]-p]]--]=sa[i]-p;
dF(i,n,n-p+1)SA[cnt[rk[i]]--]=i;
F(i,1,n)RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i-1]]!=rk[SA[i]]||rk[SA[i-1]+p]!=rk[SA[i]+p]);
F(i,1,n)sa[i]=SA[i],rk[i]=RK[i];
}
F(i,1,n){
int j=sa[rk[i]-1],k=max(0,h[i-1]-1);
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])++k;
h[i]=ht[rk[i]]=k;
}
F(i,1,n)mn[i][0]=ht[i];
F(j,1,20)F(i,1,n-(1<<j)+1)mn[i][j]=min(mn[i][j-1],mn[i+(1<<(j-1))][j-1]);
}
int qry(int l,int r){
int k=__lg(r-l+1);
return min(mn[l][k],mn[r-(1<<k)+1][k]);
}
int lcp(int x,int y){
if(x==y)return n-x+1;
if(rk[x]>rk[y])swap(x,y);
return qry(rk[x]+1,rk[y]);
}
lca
int fa[N][22],dep[N];
void dfs(int u,int par){
dep[u]=dep[par]+1;
fa[u][0]=par;
F(i,1,20) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int v:g[u]) if(v!=par) dfs(v,u);
}
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
G(i,20,0) if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if(x==y) return x;
G(i,20,0) if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
}
return fa[x][0];
}
flow
struct gph{
int n;
vector<int> he,nx,to,dep;
vector<ll> val;
gph(int n):n(n),he(n,-1),dep(n){}
void adde(int u,int v,ll w){
nx.pb(he[u]);
to.pb(v);
val.pb(w);
he[u]=si(nx)-1;
}
void add(int u,int v,ll w){
adde(u,v,w);
adde(v,u,0);
}
ll flow(int s,int t){
auto bfs=[&](){
F(i,0,n-1) dep[i]=0;
dep[s]=1;
queue<int> q;
q.push(s);
while(si(q)){
int u=q.front();
q.pop();
for(int i=he[u];~i;i=nx[i]){
ll v=to[i],w=val[i];
if(w>0&&!dep[v]){
dep[v]=dep[u]+1;
if(v==t) return 1;
q.push(v);
}
}
}
return 0;
};
ll ans=0;
while(bfs()){
function<ll(int,ll)> dfs=[&](int u,ll cur){
if(u==t) return cur;
ll res=0;
for(int i=he[u];~i;i=nx[i]){
ll v=to[i],w=val[i];
if(w>0&&dep[v]==dep[u]+1){
ll x=dfs(v,min(cur,w));
cur-=x;
res+=x;
val[i]-=x;
val[i^1]+=x;
if(!cur) break;
}
}
if(!res) dep[u]=0;
return res;
};
ans+=dfs(s,1e18);
}
return ans;
}
};
costflow
struct gph{
int n;
vector<int> he,nx,to,vis,pre;
vector<ll> f,c,d;
gph(int n):n(n),he(n,-1),vis(n),pre(n),d(n){}
void adde(int u,int v,ll x,ll y){
nx.pb(he[u]);
to.pb(v);
f.pb(x);
c.pb(y);
he[u]=si(nx)-1;
}
void add(int u,int v,ll x,ll y){
adde(u,v,x,y);
adde(v,u,0,-y);
}
pair<ll,ll> flow(int s,int t){
auto spfa=[&](){
F(i,0,n-1) vis[i]=0;
F(i,0,n-1) d[i]=4e18;
d[s]=0;
queue<int> q;
q.push(s);
while(si(q)){
int u=q.front();
q.pop();
vis[u]=0;
for(int i=he[u];~i;i=nx[i]){
int v=to[i];
if(f[i]>0&&d[u]+c[i]<d[v]){
d[v]=d[u]+c[i];
pre[v]=i;
if(!vis[v]){
vis[v]=1;
q.push(v);
}
}
}
}
return d[t]<4e18;
};
pair<ll,ll> ans;
while(spfa()){
ll mn=4e18;
for(int i=t;i!=s;i=to[pre[i]^1]) mn=min(mn,f[pre[i]]);
ans.fi+=mn;
for(int i=t;i!=s;i=to[pre[i]^1]){
f[pre[i]]-=mn;
f[pre[i]^1]+=mn;
ans.se+=mn*c[pre[i]];
}
}
return ans;
}
};
hld
int sz[N],son[N],fa[N],dep[N];
void dfs1(int u,int par){
fa[u]=par;
dep[u]=dep[par]+1;
sz[u]=1;
for(int v:g[u])if(v!=par){
dfs1(v,u);
sz[u]+=sz[v];
if(sz[v]>sz[son[u]])son[u]=v;
}
}
int tp[N],dfn[N],tim,p[N];
void dfs2(int u,int t){
dfn[u]=++tim,p[dfn[u]]=u;
tp[u]=t;
if(!son[u])return;
dfs2(son[u],t);
for(int v:g[u])if(v!=fa[u]&&v!=son[u])dfs2(v,v);
}
int lca(int x,int y){
while(tp[x]!=tp[y]){
if(dep[tp[x]]<dep[tp[y]])swap(x,y);
x=fa[tp[x]];
}
return dep[x]<dep[y]?x:y;
}
bit
struct bit{
int n,c[N];
void init(int m){
n=m;
F(i,1,n) c[i]=0;
}
void add(int i,int k){
for(;i<=n;i+=i&-i) c[i]+=k;
}
int qry(int i){
int res=0;
for(;i>=1;i-=i&-i) res+=c[i];
return res;
}
int qry(int l,int r){
return qry(r)-qry(l-1);
}
};
seg
void up(int p){
}
void ap(int p,/**/){
}
void dn(int p){
}
void upd(int s,int t,int l,int r,int p){
if(s<=l&&r<=t){
//
return;
}
int mid=(l+r)>>1;
dn(p);
if(s<=mid)upd(s,t,l,mid,p*2);
if(t>mid)upd(s,t,mid+1,r,p*2+1);
up(p);
}
int qry(int s,int t,int l,int r,int p){
if(s<=l&&r<=t)/**/;
int mid=(l+r)>>1,res=0;
dn(p);
if(s<=mid)/**/;
if(t>mid)/**/;
return res;
}
vt
sort(v.begin(),v.end(),[](int x,int y){return dfn[x]<dfn[y];});
int k=si(v);
F(i,1,k-1)v.pb(lca(v[i-1],v[i]));
sort(v.begin(),v.end(),[](int x,int y){return dfn[x]<dfn[y];});
v.resize(unique(v.begin(),v.end())-v.begin());
F(i,1,si(v)-1)g[lca(v[i-1],v[i])].pb(v[i]);