答案就是 \(n^{m-1}m^{n-1}\)

\(prufer\) 证明：

\(n\) 中的数字出现 \(m-1\) 次，\(m\) 中出现 \(n-1\) 次，根据 \(prufer\) 解码可知，\(n,m\) 中的数字和内部顺序确定了，那么它们的相对位置也可以确定

\(matrix-tree\) 证明：

构建基尔霍夫矩阵，去掉第一行第一列，发现分成四个部分

左上角 \((n-1)\times (n-1)\)，主对角线为 \(m\)，其余为 \(0\)

右下角 \(m\times m\)，主对角线为 \(n\)，其余为 \(0\)

左下右上都是 \(-1\)

手动求行列式

把第 \(n\) 行加上前 \(n-1\) 行，变成

\[m-1,m-1,...,m-1,1,1-n,1-n,...,1-n\]

再加上后 \(m-1\) 行，变成

\[0,0,...,0,1,1,1,...,1\]

依次加到前 \(n-1\) 行中，变成了下三角

对角线上有 \(1\) 个 \(1\)，\(n-1\) 个 \(m\)，\(m-1\) 个 \(n\)

代码不贴了，直接快速幂+龟速乘即可