问题描述：

在一串未打结的项链上(意思就是说项链的左端和右端不相连)，有N颗珠子，你有M种颜色，然后就问你有多少种方法将每一颗珠子都染上颜色，使得任意两颗相邻的珠子的颜色不同。当然，你不要想太多，请不要考虑Polya之类的本质相同.

输入格式

输入只有一行，三个正整数N、M和P，之间以一个空格隔开。

输出格式

输出只有一行，表示染色的方法总数模P。(即MOD P)

输入样例：

5 4 13

输出样例：

12

(样例说明：一共有324种染色方法，对13取模后是12。)

数据范围：

对于10%的数据，N=1，M<=10，P<=10；

对于20%的数据，N<=10，M<=10，P<=100；

对于50%的数据，N,M,P<=1,000,000,000；

对于100%的数据，1<=N,M,P<=1,000,000,000,000,000,000，且M>=2。