最后这个转化非常牛逼啊！
首先我们可以证明：一个合法的序列中，这样的极长连续区间不会相交。
Proof：如果相交了，说明相交的区间也是一段连续区间，而每个区间不相交的部分也是连续区间，所以两个区间的并也是连续区间。又因为两个区间都是极长连续区间，因此不会包含，所以与题设的”极长”矛盾。
因此现在区间只剩下相互包含和互不相交两种。把这个建成一个树的结构，可以发现一个区间的儿子覆盖了整个区间，除了最后一个位置。因此如果我们可以求出 \(g_i\) 表示 \(i+1\) 个数排列在一起，除了最后一个位置的连续区间长度为全区间，其余都为 \(1\) 的排列个数，方案数就是 \(\prod{g_{siz_i}}\)，其中 \(siz_i\) 表示 \(i\) 的儿子个数。
现在压力来到了 \(g\) 身上。直接对 \(g\) 计数也不好做。考虑对 \(p\) 的转置计数，也即 \(q_{p_i}=i\)。\(p\) 的原来的限制转化过来就是除了包含最大值的连续区间，其余连续区间长度都为 \(1\)。
考虑对 \(2\dots n+1\) 序列插入 \(1\) 来完成 \(n\) 到 \(n+1\) 的转移。分两种情况：
- 序列原来是合法的区间，那么除了插入在 \(2\) 两边都可以，因此有转移 \(f_{i}\times i\to f_{i+1}\)。
- 序列原来是不合法的区间，那么原来的连续区间都要包含 \(1\) 的位置，且连续区间中不包含 \(2\) 。枚举最大的连续区间的长度，有转移 \(f_{j}f_{i-j}(j-1)\to f_i\)。
直接暴力\(O(n^2)\) 的 dp 可以有 \(80\) 分。优化的话直接上分治 NTT 就可以做到 \(O(n\log ^2n)\)。注意这里是自己乘自己转移到自己，和普通的分治 NTT 有所不同。
code:
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
#define fi first
#define se second
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;
using namespace std;const int N=(1<<18)+5,M=N*100+5,K=N*4+5,mod=998244353,Mod=mod-1;const db eps=1e-9;const ll INF=1e18+7;mt19937 rnd(time(0));
int n,m,k,x,y,z,A[N];ll f[N];
void Solve(){
int i,j;ll Ans=1;for(i=1;i<=n;i++) scanf("%d",&A[i]);
for(i=1;i<=n;i++){
int x=i-1,Ct=0;
while(x>=i-A[i]+1) Ct++,x-=A[x];
if(x<i-A[i]){puts("0");return ;}Ans=Ans*f[Ct]%mod;
}
if(A[n]^n){puts("0");return;}
printf("%lld\n",Ans);
}
ll mpow(ll x,int y=mod-2){ll Ans=1;while(y) y&1&&(Ans=Ans*x%mod),y>>=1,x=x*x%mod;return Ans;}
namespace Poly{
int tr[N];const int g=3,Ig=mpow(g);
ll C[N],D[N];
void Init(int n){for(k=1;k<=n;k<<=1);for(int i=0;i<k;i++) tr[i]=(tr[i>>1]>>1)|(i&1?k/2:0),C[i]=D[i]=0;}
void NTT(ll *A,int k,int op){
int i,j,h;ll key,now,pus;for(i=0;i<k;i++) if(i<tr[i]) swap(A[i],A[tr[i]]);
for(i=2;i<=k;i<<=1){
for(key=mpow(op?g:Ig,(mod-1)/i),j=0;j<k;j+=i){
for(pus=1,h=j;h<j+i/2;h++) now=pus*A[h+i/2]%mod,A[h+i/2]=(A[h]+mod-now)%mod,A[h]=(A[h]+now)%mod,pus=pus*key%mod;
}
}if(op) return;ll In=mpow(k);for(i=0;i<k;i++) A[i]=A[i]*In%mod;
}
void Solve(int l,int r){
if(l==r) {f[l]=(f[l]+f[l-1]*(l-1))%mod;return;}int m=l+r>>1,i;Solve(l,m);
if(l==2){
Init(r-l+1+m-l+1);
for(i=2;i<=m;i++) C[i]=f[i]*(i-1)%mod;for(i=l;i<=m;i++) D[i-l]=f[i];
NTT(C,k,1);NTT(D,k,1);for(i=0;i<k;i++) C[i]=C[i]*D[i]%mod;NTT(C,k,0);for(i=m+1;i<=r;i++) f[i]=(f[i]+C[i-l])%mod;
}else{
Init(r-l+1+m-l+1);
for(i=2;i<=r-l;i++) C[i]=f[i];for(i=l;i<=m;i++) D[i-l]=f[i];
NTT(C,k,1);NTT(D,k,1);for(i=0;i<k;i++) C[i]=C[i]*D[i]%mod;NTT(C,k,0);for(i=m+1;i<=r;i++) f[i]=(f[i]+C[i-l]*(i-2))%mod;
}
Solve(m+1,r);
}
}
int main(){
freopen("1.in","r",stdin);
int t,i,j;scanf("%d%d",&t,&n);f[0]=1;f[1]=2;if(n>1) Poly::Solve(2,n);
/* for(i=2;i<=n;i++) {
f[i]=f[i-1]*(i-1)%mod;
for(j=2;j<i-1;j++) f[i]=(f[j]*f[i-j]%mod*(j-1)+f[i])%mod;
}*/
while(t--) Solve();
}