B

$BB$

将$[1,n][1,\; n]$的数看作$00$，将$[n+1,2n][n+1,\; 2n]$的数看作$11$，则任何$1010$，或者$0101$都是合法的，只有$0000$或者$1111$有可能会不合法，设$[i][j][0\mathrm{/}1][i][j][0/1]$表示考虑了前$ii$个，第$ii$个为$0\mathrm{/}10/1$时，共用了$jj$个$00$的合法方案数，转移方程考虑枚举$ii$往前是一连串的$00$或者$11$，枚举从哪里转移而来，若由$f[k][x][y]f[k][x][y]$转移而来，那么在$[k+1,i][k+1,i]$这个区间全是$00$或者$11$，考虑合法方案这一段的填的数（从剩余的数中取这个区间长度的数出来）大小是固定的即从大到小或者从小到大放置，考虑到$ii$位置才不合法，则这一段数除了最小/最大的不能放在$ii$（否则就合法），其它的都可以，然后令剩下的数按照合法顺序放即可，最后$ii$后面可以随便放，于是不合法方案就可以算出来了

code

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 605;
int T, n, n2, m;
int fac[maxn];
int c[maxn][maxn];
int f[maxn][maxn][2];
void init ()
{
    fac[0] = c[0][0] = 1;
    for (int i = 1; i <= n2; ++i)	fac[i] = 1ll * fac[i - 1] * i % m;
    for (int i = 1; i <= n2; ++i) {
        c[i][0] = 1;
        for (int j = 1; j <= i; ++j)
            c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % m;
    }
    for (int i = 1; i <= n2; ++i)
        for (int j = 0; j <= n2; ++j)    f[i][j][0] = f[i][j][1] = 0;
}
int main ()
{
    scanf("%d", &T);
while (T--) {
    scanf("%d%d", &n, &m);
    n2 = n << 1;
    init();
    f[0][0][0] = f[0][0][1] = 1;
    int ans = 0;
    for (int i = 1; i <= n2; ++i) {
        for (int j = min(i, n); j >= 0; --j) {
            for (int k = i - 1; k >= 0; --k) {
                int t0 = j - (i - k);
                if (t0 < 0 || t0 > min(k, n))	continue;
                f[i][j][0] += 1ll * f[k][t0][1] * c[n - t0][i - k] % m;
                f[i][j][0] %= m;
                ans += 1ll * f[k][t0][1] * c[n - t0][i - k] % m * (i - k - 1) % m * i % m * fac[n2 - i] % m;
                ans %= m;
            }
            for (int k = i - 1; k >= 0; --k) {
                int t1 = (i - j) - (i - k);
                if (t1 < 0 || t1 > min(n, k))	continue;
                
                f[i][j][1] += 1ll * f[k][j][0] * c[n - t1][i - k] % m;
                f[i][j][1] %= m;
                ans += 1ll * f[k][j][0] * c[n - t1][i - k] % m * (i - k - 1) % m * i % m * fac[n2 - i] % m;
                ans %= m;
            }
        }
    }
    ans += (1ll * f[n2][n][0] * n2 % m + 1ll * f[n2][n][1] * n2 % m) % m;
    ans %= m;
    printf("%d\n", ans);
}
    return 0;
}