https://codeforces.com/contest/1957/problem/C
题面：
题解：
补充说明：
把n阶棋盘想成n-1阶和外面套了一圈的如上图
则可以分成下面两种情况：
1.
下在（1，1）处，那么为dp[n-1]
2.
从(1,2)...(1,n-1)|(2,1)...(n-1,1)共有n-1种显然为2(n-1)dp[n-2]
那么递推：
dp[n]=dp[n-1]+2*(n-1)*dp[n-2]
代码：
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<sstream>
#include<string>
#include<string.h>
#include<iomanip>
#include<stdlib.h>
#include<map>
#include<queue>
#include<limits.h>
#include<climits>
#include<fstream>
#include<stack>
#include<set>
typedef long long ll;
using namespace std;
const ll mod = 1e9 + 7;
ll dp[300010];
ll dpp(ll n)
{
if (dp[n])return dp[n];
ll res = 0;
res = dpp(n - 1) + (n - 1 ) * 2 * dpp(n - 2);
res %= mod;
return dp[n] = res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
dp[1] = 1;
dp[2] = 3;
while (t--)
{
ll n; cin >> n;
int k; cin >> k;
for (int i = 0; i < k; i++)
{
int x, y; cin >> x >> y;
if (x == y)n--;
else n -= 2;
}
if (n == 0)cout << 1 << endl;
else cout << dpp(n) << endl;
}
return 0;
}