不是为什么套路题没有人切呀？？？

注意到我写加调这道题的时间远小于写加调这场的T3

首先看见这个什么可以交流的对数，直接套路转化成联通块的个数，我们定义一段是联通的，当且仅当这一段数字相邻相差为1

然后我们随便瞎设一个状态 $F_{i,j,{0/1}}$ 表示我现在放了前 $i$ 个数，然后我放出来了 $j$ 个联通块，然后我最后一个数是(1)不是(0)与其他点连接。

然后就随便讨论

然后就做完了

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;
long long f[1005][1005][2];
int main(){
	freopen("count.in","r",stdin);
	freopen("count.out","w",stdout);
	int T;scanf("%d",&T);
	int n=1000;f[1][1][0]=1;
	for(int i=2; i<=n; i++){
		for(int j=1; j<i; j++){
			f[i][j+2][0]=(f[i][j+2][0]+f[i-1][j][0]*(i-j-1)%mod+f[i-1][j][1]*(i-j-2))%mod;
			f[i][j+1][0]=(f[i][j+1][0]+f[i-1][j][0]*(j-1)%mod+f[i-1][j][1]*(j)%mod)%mod;
			f[i][j+1][1]=(f[i][j+1][1]+f[i-1][j][1])%mod;
			f[i][j][1]=(f[i][j][1]+f[i-1][j][0]*2+f[i-1][j][1])%mod;
		}
	}
	while(T--){
		int n,K;scanf("%d%d",&n,&K);
		printf("%d\n",(f[n][n-K][0]+f[n][n-K][1])%mod);
	}
	return 0;
}

点名批评 $Weily$ ，因为我清楚地记得类似的 $trick$ NH之前出过，而且他当时说没有想出来是时间问题