[扫地杯S3]染色问题

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 colora.in 输出文件 colora.out

【题目描述】

做了HEOI2012的赵州桥(bridge)之后，liouzhou_101就感到极其的不爽，首先那题题目叙述巨渣，然后做法极坑。

不过那题是一道和染色有关的问题，于是在此同时也启发liouzhou_101想到了这样一个简单的问题：

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

liouzhou_101这种傻×自然不会做了，于是来向你请教…

当然，由于liouzhou_101的脑子构造极其简单，你不要想太多，请不要考虑Polya之类的本质相同，否则的话仅凭liouzhou_101的理解能力是不能理解的…

【输入格式】

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

【输出格式】

输出只有一行，表示染色的方法总数模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。

【来源】

http://www.tyvj.cn/Problem_Show.aspx?id=2043