【题目】
题目描述：
“奋战三星期，造台计算机”。小 W 响应号召，花了三星期造了台文艺计算姬。
文艺计算姬比普通计算机有更多的艺术细胞。 普通计算机能计算一个带标号完全图的生成树个数，而文艺计算姬能计算一个带标号完全二分图的生成树个数。
更具体地，给定一个一边点数为
n
n
n
，另一边点数为
m
m
m
，共有
n
∗
m
n*m
n
∗
m
条边的带标号完全二分图
k
n
,
m
k_{n,m}
k
n
,
m
，计算姬能快速算出其生成树个数。
小 W 不知道计算姬算的对不对，你能帮助他吗？
输入格式：
仅一行三个整数
n
,
m
,
p
n,m,p
n
,
m
,
p
，表示给出的完全二分图
k
n
,
m
k_{n,m}
k
n
,
m
。
输出格式：
仅一行一个整数，表示完全二分图
k
n
,
m
k_{n,m}
k
n
,
m
的生成树个数，答案需要模
p
p
p
。
样例数据：
输入
2 3 7
输出
5
备注：
【数据范围】
20% 的数据：
n
∗
m
≤
20
n*m ≤ 20
n
∗
m
≤
2
0
另有 10% 的数据：
n
=
2
n=2
n
=
2
另有 20% 的数据：
n
=
3
,
m
≤
1
0
6
n=3 , m≤10^6
n
=
3
,
m
≤
1
0
6
另有 20% 的数据：
n
=
4
n=4
n
=
4
100% 的数据：
1
≤
n
,
m
,
p
≤
1
0
18
1 ≤n,m,p ≤ 10^{18}
1
≤
n
,
m
,
p
≤
1
0
1
8
【分析】
直接说结论吧，最后的答案
a
n
s
=
m
n
−
1
⋅
n
m
−
1
  
m
o
d
  
p
ans=m^{n-1}\cdot n^{m-1} \;mod\;p
a
n
s
=
m
n
−
1
⋅
n
m
−
1
m
o
d
p
当然，这个东西我是没有推出来的，我们老师直接给我们说了结论，让我们当成快速幂板子做
注意两个
l
o
n
g
  
l
o
n
g
long\;long
l
o
n
g
l
o
n
g
相乘很可能会爆
l
o
n
g
  
l
o
n
g
long\;long
l
o
n
g
l
o
n
g
的范围，我们要用
快速积
来防止爆精度
【代码】
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
long long n,m,p;
long long Multiply(long long a,long long b,long long c)
{
long long ans=0,res=a;
while(b)
{
if(b&1)
ans=(ans+res)%c;
res=(res+res)%c;
b>>=1;
}
return ans;
}
long long Power(long long a,long long b,long long c)
{
long long ans=1,res=a;
while(b)
{
if(b&1)
ans=Multiply(ans,res,c);
res=Multiply(res,res,c);
b>>=1;
}
return ans;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&p);
printf("%lld",Multiply(Power(n,m-1,p),Power(m,n-1,p),p));
return 0;
}