题目描述

在进香河，流传着这样一段美丽的故事。$zyg$与$kzn$是两个生活在进香河的孩子，一天，他们两人闹矛盾了，于是$zyg$送给了$kzn$一条精美的爱之项链。从此他们幸福生活在一起。

这则故事的真实性到今天已经没有意义了，然而我们关注的是那一条精美的爱之项链。这是一条由$N$个精致的戒指与一块特殊纪念品相连而成的环形，如下图中的爱心符号正是一种特殊纪念品。(据说是$2012$年情人节时$zyg$特意托人订制的)上面的每一枚戒指又是由$M$个带磁性的特殊彩色球状物组成的环形。也许你会认为，这所谓的戒指，更像是一条条小项链。

下图给出了一种可行的方案，其中左边描述的是单一的一枚戒指，右图描述的是项链。

这里，所有带磁性的特殊彩色球状物的颜色只有$R$种，这里我们用$1$到$R$来表示。如果一枚戒指可以通过顺时针或逆时针的旋转后与另外一枚戒指相同，则认为这是两枚相同的戒指。

对于一条爱之项链，要求满足任何相邻两枚戒指必须是不相同的。同时，特殊纪念品左右两枚戒指也必须是不同的。

现在给定$N$，$M$和$R$，问究竟有多少种不同的爱之项链。

注意：

$1$、特殊纪念品的插入位置不同，也许会得到不同的爱之项链。

$2$、这里我们只考虑旋转后是否相同，不考虑翻转操作，这一点不论是对于每一枚戒指，还是对于整条项链，都是这样的。

输入格式

一行，三个正整数，分别是$N$，$M$和$R$。

输出格式

一行，表示有多少种不同的爱之项链。你只需要将答案模$3214567$。

10 5 4

1398595

提示

对于$30\%$的数据，$N \leq 10^3$，$M \leq 3 \times 10^2$，$R \leq 10^2$。

对于$60\%$的数据，$N \leq 3 \times 10^4$，$M \leq 2 \times 10^3$，$R \leq 10^5$。

对于$80\%$的数据，$N \leq 10^7$，$M \leq 10^6$，$R \leq 10^6$。

对于$100\%$的数据，$N \leq 10^{15}$，$M \leq 10^9$，$R \leq 10^6$。