Description

"奋战三星期，造台计算机"。小W响应号召，花了三星期造了台文艺计算姬。文艺计算姬比普通计算机有更多的艺术细胞。

普通计算机能计算一个带标号完全图的生成树个数，而文艺计算姬能计算一个带标号完全二分图的生成树个数。

更具体地，给定一个一边点数为n，另一边点数为m，共有n*m条边的带标号完全二分图K_{n,m}，计算姬能快速算出其生成树个数。

小W不知道计算姬算的对不对，你能帮助他吗？

Input

仅一行三个整数n,m,p，表示给出的完全二分图K_{n,m}

1 <= n,m,p <= 10^18

Output

仅一行一个整数，表示完全二分图K_{n,m}的生成树个数，答案需要模p。

Sample Input

2 3 7

Sample Output

5

Solution

首先先把(度数矩阵-邻接矩阵)搞出来，这里以样例为例。

$

\left\{

\begin{matrix}

3&0&-1&-1&-1\\

0&3&-1&-1&-1\\

-1&-1&2&0&0\\

-1&-1&0&2&0\\

-1&-1&0&0&2\\

\end{matrix}

\right\}

$

按照求矩阵树的方法随便删掉一行一列，这里删掉了最后一行和最后一列。

$

\left\{

\begin{matrix}

3&0&-1&-1\\

0&3&-1&-1\\

-1&-1&2&0\\

-1&-1&0&2\\

\end{matrix}

\right\}

$

把前$n-1$行和后$m-1$行都加到第$n$行

$

\left\{

\begin{matrix}

3&0&-1&-1\\

1&1&0&0\\

-1&-1&2&0\\

-1&-1&0&2\\

\end{matrix}

\right\}

$

用第$n$行的去加到后面$m-1$行上，把$-1$给消掉。

$

\left\{

\begin{matrix}

3&0&-1&-1\\

1&1&0&0\\

0&0&2&0\\

0&0&0&2\\

\end{matrix}

\right\}

$

这样的话这个矩阵的行列式显然就是$m^{n-1}n^{m-1}$了。

记得快速乘。

Code

1 #include
     
       2 #define LL long long  3 using namespace std; 4  5 LL n,m,p; 6  7 LL Mul(LL a,LL b) 8 { 9     LL tmp=a*b-(LL)((long double)a*b/p+0.1)*p;10     return tmp<0?tmp+p:tmp;11 }12 13 LL Qpow(LL a,LL b)14 {15     LL ans=1;16     while (b)17     {18         if (b&1) ans=Mul(ans,a);19         a=Mul(a,a); b>>=1;20     }21     return ans;22 }23 24 int main()25 {26     scanf("%lld%lld%lld",&n,&m,&p);27     printf("%lld",Mul(Qpow(n,m-1),Qpow(m,n-1)));28 }