引用题解：
#include <cstdio>
#define maxn 105
#define mod 9999973
#define ll long long
using namespace std;
ll n,m,dp[maxn][maxn][maxn],ans;
int C(int num){
return (num*(num-1)/2)%mod;
}
int main(){
scanf("%lld%lld",&n,&m);
dp[0][0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=m-j;k++){
dp[i][j][k]=dp[i-1][j][k];//当前行 一颗棋子都不放
if(k>=1)dp[i][j][k]+=dp[i-1][j+1][k-1]*(j+1);//在 放了一个棋子的列 放一个棋子 使当前列 变成有两个棋子的列
if(j>=1)dp[i][j][k]+=dp[i-1][j-1][k]*(m-j-k+1);//在 没有放棋子的列 放一个棋子
/*
为何是m-j-k+1呢
因为剩下 可以选择的列是m-j-k+1 ，当前的j 表示已经在没有棋子的列 放了一个棋子后 产生的
m-j-k 表示 在 没有棋子的一列 放了一个棋子之后 还有多少空着的列
m-j-k+1 则在上面的基础上 多了一列空闲列 ，也就是 上一步的 推过来 还没有 具体操作
*/
if(k>=2)dp[i][j][k]+=dp[i-1][j+2][k-2]*((j+2)*(j+1)/2);//分别在有一个棋子的两列 各放置一个棋子
if(k>=1)dp[i][j][k]+=dp[i-1][j][k-1]*j*(m-j-k+1);//在有一个棋子的一列放一个棋子，再在没有棋子的一列放已给棋子
if(j>=2)dp[i][j][k]+=dp[i-1][j-2][k]*C(m-j+2-k);// 分别在没有棋子的两列 各放置一个棋子
dp[i][j][k]%=mod;
}
}
}
//printf("%d",dp[1][2][0]); 样例 是 dp[1][0][0]+dp[1][1][0]+dp[1][2][0] = 1 + 3 + 3
for(int i=0;i<=m;i++)
for(int j=0;j<=m;j++)
(ans+=dp[n][i][j])%=mod;
printf("%lld",(ans+mod)%mod);
return 0;
}