Description：

设 $L[i]$ 表示右端点在 $i$ 的最长连续段的长度，给出 $L$ 数组，问有多少个排列满足它。

$1\leqslant n\leqslant 50000,1\leqslant t\leqslant 100$

Solution：

首先先把无解判掉，如果 $L[n]\ne n$ 或者两个区间相交但是不包含就无解。

然后把每个点向长度最小的包含他的区间连边，这样一定会构成一棵树，意为包含每个区间的最短连续区间是一定的，然后我们就要在这棵树上计数，注意这棵树和析合树不太一样，先预处理一个 $f[i]$ 表示 $\forall k\in [1,i],L[k]=1$ 并且最后还有一个元素 $i+1$ 可以有任意长度的连续段 $i$ 阶排列数量，假如我们已经求出了这个，我们就可以在树上 $DP$ ： $$ dp[k]=f(|son[k]|)\times \prod_{v\in son[k]}dp[v] $$ 观察一下其实答案就是 $\prod_k |son[k]|$ 。

于是现在我们只要解决求 $f[k]$ 的问题就行了，假如我们已经知道了 $f[i]$ ，考虑新加一个儿子，并且这个儿子是最大的，分两种情况讨论：

1、 $1\sim i$ 是一个合法的排列，此时我们只要不在 $i$ 的两边插入 $i+1$ 就行了，因为 $i$ 必然不在最后一位，不然的话前面所有儿子都成为了一个连续段，方案数为 $(i-1)\times f[i-1]$ 。

2、 $1\sim i$ 不是一个合法的排列，也就是说原来有连续段，后来没了，那么原来至多有一个连续段因为如果原来有多个连续段的话，无论他们相交还是不相交，都一定不可能跨过同一个点，因此原来至多有一个连续段，而且这个连续段的最大值不能是 $i$ ，因为如果是的话，加入 $i+1$ 不能把他们分开，那我们可以枚举这个连续段插入 $i+1$ 的位置之前的长度为 $j$ ，再插入 $i+1$ 这个连续段有 $f[j]$ 种方案，把它看成一个点那么就有 $i-j+1$ 个点，他们的方案为 $f[i-j]$ ，然后就相当于我们现在有了一个 $i-j+1$ 阶排列，我们要选一个数插入 $i+1$ ，首先显然 $i+1$ 不能插入最大的一段，因为这样不能把一个原来的连续段拆开，然后也不能是最后一段，因为 $j$ 是前半部分还要有后半部分，于是可以拆开的段就只有 $i-j-1$ 个，于是得到转移： $$ f[i]=(i-1)\times f[i-1]+\sum_{j=1}^{i-2}(i-j-1)f[j]f[i-j] $$ 之所以 $j$ 的范围是 $1\sim i-2$ 是因为必须比整个小一。

注意这个分治 $FFT$ 是一个 我卷我自己 ，因此每次考虑 $[l,mid]$ 作为卷积中较大的那一项的贡献，具体看代码。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int t,n;

#define MAXN 200010

int f[MAXN];

#define P 998244353

int a[MAXN],b[MAXN];

int ww[MAXN << 1],*g = ww + MAXN;

int rev[MAXN];

#define R register

#define I inline

I int rd()

{

	R int res = 0,f = 1;R char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int power(int a,int b)

{

	R int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % P;

		a = 1ll * a * a % P;

		b = b >> 1;

	}

	return res;

}

int init(int n)

{

	R int l = 0,len = 1;

	for(;len <= n;len = len << 1)++l;

	for(R int i = 0;i < len;++i)rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (l - 1));

	g[0] = g[-len] = 1;g[1] = g[1 - len] = power(3,(P - 1) / len);

	for(R int i = 2;i < len;++i)g[i] = g[i - len] = 1ll * g[i - 1] * g[1] % P;

	return len;

}

void NTT(int f[],int l,int type)

{

	for(R int i = 0;i < l;++i)

	{

		if(i < rev[i])swap(f[i],f[rev[i]]);

	}

	for(R int i = 2;i <= l;i = i << 1)

	{

		R int wn = g[type * l / i];

		for(R int j = 0;j < l;j += i)

		{

			R int w = 1;

			for(R int k = j;k < j + i / 2;++k)

			{

				R int u = f[k],t = 1ll * w * f[k + i / 2] % P;

				f[k] = (u + t) % P;

				f[k + i / 2] = (u - t + P) % P;

				w = 1ll * w * wn % P;

			}

		}

	}

	if(type == -1)

	{

		R int ni = power(l,P - 2);

		for(R int i = 0;i < l;++i)f[i] = 1ll * f[i] * ni % P;

	}

	return;

}

void solve(int l,int r)

{

	if(l == r){f[l] = (f[l] - 1ll * f[l - 1] * (l - 3) % P + P) % P;return;}

	R int mid = ((l + r) >> 1);

	solve(l,mid);

	for(R int i = 0;i <= mid - l;++i)b[i] = f[i + l];

	for(R int i = 0;i <= min(r - l,l - 1);++i)a[i] = f[i];

	R int len = init((r - l) * 2);

	NTT(a,len,1);NTT(b,len,1);

	for(R int i = 0;i < len;++i)a[i] = 1ll * a[i] * b[i] % P;

	NTT(a,len,-1);

	for(R int i = mid + 1;i <= r;++i)f[i] = (f[i] + 1ll * a[i - l] * (i - 2) % P) % P;

	for(R int i = 0;i < len;++i)a[i] = b[i] = 0;

	for(R int i = l;i <= min(mid,r - l);++i)a[i] = f[i];

	for(R int i = 0;i <= mid - l;++i)b[i] = 1ll * f[i + l] * (i + l - 1) % P;

	len = init((r - l) * 2);

	NTT(a,len,1);NTT(b,len,1);

	for(R int i = 0;i < len;++i)a[i] = 1ll * a[i] * b[i] % P;

	NTT(a,len,-1);

	for(R int i = mid + 1;i <= r;++i)f[i] = (f[i] + a[i - l]) % P;

	for(R int i = 0;i < len;++i)a[i] = b[i] = 0;

	solve(mid + 1,r);

	return;

}

int L[MAXN];

int stack[MAXN],top = 0;

int siz[MAXN];

void work()

{

	for(int i = 1;i <= n;++i)L[i] = rd();

	if(L[n] != n)

	{

		puts("0");

		return;

	}

	for(int i = 1;i <= n;++i)siz[i] = 0;

	top = 0;

	for(int i = n;i >= 1;--i)

	{

		while(top > 0 && stack[top] - L[stack[top]] + 1 > i - L[i] + 1)

		{

			if(stack[top] - L[stack[top]] + 1 <= i){puts("0");return;}

			--top;

		}

		++siz[stack[top]];

		stack[++top] = i;

	}

	int ans = 1;

	for(int i = 1;i <= n;++i)ans = 1ll * ans * f[siz[i]] % P;

	cout << ans << endl;

	return;

}

int main()

{

	scanf("%d%d",&t,&n);

	f[0] = 1;solve(1,n);

	while(t--)work();

	return 0;

}