神秘。

首先这个操作可以直接换成我们比较熟悉的如果 $|a_i-a_{i+1}| \leq 1$ 就交换 $a_i,a_{i+1}$。

因为是对序列计数每所不妨只允许 $|a_i-a_{i+1}|=1$ 的交换。

现在就从对序列计数变成了对交换后的序列中每个数原来所处的位置构成的序列计数。

考虑转写一下性质把交换这件事整个丢掉，注意到如果存在 $i<j,|a_i - a_j| \not = 1$ 那么 $j$ 永远在 $i$ 后面，考虑对于所有这样的 $i,j$ 建边 $i \to j$，问题转变为这张图的拓扑序计数。

看上去不太能做，感受一下，发现这张图理论上比较密，因为边大概率特别多，考虑把这些边放在一起看，观察其是怎么影响答案的。

不难发现如果存在一条链 $p_1 \to p_2 \to p_3 \to \dots \to p_k$，那么 $p_1,p_2,p_3,\dots,p_k$ 一定是最终拓扑序的一个子序列。

再注意到按照奇偶性给 $h_i$ 分类之后，所有点被划分到了两条链中，那么拓扑序产生的过程实际上就是归并两条链的过程，$O(n^2)$ dp 一下即可，具体细节可以看代码。

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
const int maxn = 5e3+114;
int h[maxn],n;
int dp[maxn][maxn];
vector<int> pos[2];
short pre[maxn][maxn][2];//pre[i][j][t] 前缀 [1,i] 值域 [1,h[j]-2] 并 [h[j]+2,inf] 类型为 t 的 pos max
void work(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>h[i],pos[h[i]&1].push_back(i);
    for(int j=1;j<=n;j++){
        for(int i=1;i<=pos[0].size();i++){
            pre[i][j][0]=max(pre[i-1][j][0],(short)((h[pos[0][i-1]]<=h[j]-2||h[pos[0][i-1]]>=h[j]+2)?pos[0][i-1]:0));
        }
        for(int i=1;i<=pos[1].size();i++){
            pre[i][j][1]=max(pre[i-1][j][1],(short)((h[pos[1][i-1]]<=h[j]-2||h[pos[1][i-1]]>=h[j]+2)?pos[1][i-1]:0));
        }
    }
    dp[0][0]=1;
    for(int i=0;i<=pos[0].size();i++){
        for(int j=0;j<=pos[1].size();j++){
            //cerr<<i<<" "<<j<<" "<<dp[i][j]<<"\n";
            if(i<pos[0].size()){
                if(pos[0][i]>pre[j][pos[0][i]][1]) dp[i+1][j]=(dp[i+1][j]+dp[i][j])%mod; 
            }
            if(j<pos[1].size()){
                if(pos[1][j]>pre[i][pos[1][j]][0]) dp[i][j+1]=(dp[i][j+1]+dp[i][j])%mod;
            }
        }
    }
    cout<<dp[pos[0].size()][pos[1].size()]<<"\n";
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++) dp[i][j]=pre[i][j][0]=pre[i][j][1]=0;
    pos[0].clear(),pos[1].clear();
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--) work();
    return 0;
}