Eva

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 996  Solved: 568
Description

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

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

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

速算出其生成树个数。小W不知道计算姬算的对不对，你能帮助他吗？

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

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

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

2 3 7

5

/**************************************************************

    Problem: 4766

    User: ictsing

    Language: C++

    Result: Accepted

    Time:0 ms

    Memory:1292 kb

****************************************************************/

 

//BZOJ4766 文艺计算姬

#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

ll n,m,mod;

inline ll readll()

{

    ll num=0,flag=1;

    char ch;

    do{

       ch=getchar();

       if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

       num=num*10+ch-'0';

       ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void modmod(ll &x)

{

    if(x>=mod) x-=mod;

}

ll quickmul(ll a,ll b)

{

    ll res=0;

    while(b)

    {

        if(b&1) modmod(res+=a);

        modmod(a+=a),b>>=1;

    }

    return res;

}

ll quickpow(ll a,ll b)

{

    ll res=1;

    while(b)

    {

        if(b&1) res=quickmul(res,a);

        a=quickmul(a,a),b>>=1;

    }

    return res;

}

int main()

{

    n=readll(),m=readll(),mod=readll();

    printf("%lld\n",quickmul(quickpow(n,m-1),quickpow(m,n-1)));

    return 0;

}