逐行 DP ,一行一行扫下去,显然之前选择的是那几列不重要,重要的是有多少列已经放了一个棋子,多少列已经放了两个棋子。

用 $f[k][i][j]$ 表示到第 $k$ 行为止,有 $i$ 行放了一个棋子, $j$ 行放了两个棋子的方案数,没放棋子的行数可以由此推出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long
using namespace std;

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 110;
const int p = 9999973;

int n, m, ans;
int f[maxn][maxn][maxn];
ll inv2;

int C(int x) { return inv2 * x % p * (x - 1) % p; }
ll inv(ll x) {
if (x == 0 || x == 1) return 1;
return (p - p / x) * inv(p % x) % p;
}

int main() {
inv2 = inv(2);
n = read(), m = read();
f[0][0][0] = 1;
for (int k = 0; k <= n; k++)
for (int i = 0; i <= m; i++)
for (int j = 0; i + j <= m; j++) {
(f[k + 1][i][j] += f[k][i][j]) %= p;
(f[k + 1][i + 1][j] += 1LL * f[k][i][j] * (m - i - j) % p) %= p;
(f[k + 1][i + 2][j] += 1LL * f[k][i][j] * C(m - i - j) % p) %= p;
(f[k + 1][i][j + 1] += 1LL * f[k][i][j] * (m - i - j) % p * i % p) %= p;
(f[k + 1][i - 1][j + 1] += 1LL * f[k][i][j] * i % p) %= p;
(f[k + 1][i - 2][j + 2] += 1LL * f[k][i][j] * C(i) % p) %= p;
}
for (int i = 0; i <= m; i++)
for (int j = 0; i + j <= m; j++)
(ans += f[n][i][j]) %= p;
printf("%d\n", ans);
return 0;
}