前置知识：Prufer 序列，二分图
别的题解都是直接给答案，没有比较易懂的思路。
首先，考虑 Prufer 序列，发现右边点删除一定会加入一个左边点，另一边类似。
且生成 Prufer 序列的最后一定会留下左右边各一个点。
所以左边点在 Prufer 序列中出现的次数即为 \(m-1\)，右边即为 \(n-1\)。
所以这样看似乎有 \({{n+m-2}\choose{n-1}}\times n^{m-1}\times m^{n-1}\) 种 Prufer 序列。
然而这样并不正确，因为会算重，例如：
和
它们的 Prufer 序列分别为 411 和 141，但是，这两个实际上对应着同一张二分图。
这里的【二分图不同】指的是区分同侧的点，不区分两侧的点
本质上就是说，如何规定左右两边点的编号固定。
可以这样构造：
- 每次选个数多的一边，若两边个数一样就选和上次不一样的
- 找到这一边的最小叶子编号的节点删除
容易得到这样构造个数多的一边一定有叶子，且不同的方案对应不同的删除顺序。
反之，对于一个长度为 \(m-1\)，值域为 \([1,n]\cap N\) 的序列 \(a\)，以及另一个序列 \(b\)。
不妨认为 \(n\le m\)，则先从 \(a\) 开始，计算度数，选出 \(b\) 中度数为 \(1\) 的最小编号节点与 \(a_i\) 连边，然后换到另一侧进行，最后剩下的两个点直接相连即可。
这样每个点仅有一个父亲，容易发现是一颗树，且不同的序列页对应着不同的树。
于是，可以建立起两者的双射。
故答案即为 \(n^{m-1}\times m^{n-1}\)。
代码
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using big=__int128;
ll n,m,mod;
ll mul(ll x,ll y){
return (big)x*y%mod;
}
ll qpow(ll x,ll y){
ll ans=1;
for(;y;x=mul(x,x),y>>=1)if(y&1)ans=mul(ans,x);
return ans;
}
int main(){
cin>>n>>m>>mod;
cout<<mul(qpow(n,m-1),qpow(m,n-1));
return 0;
}