Problem Description

In Jingxiang River, there is a beautiful story. zyg and kzn are two children who live in Jingxiang River. One day, they had a quarrel, so zyg gave kzn an exquisite Necklace of Love. From then on, they lived happily together.

Whether this story is true no longer matters today. What we care about is that exquisite Necklace of Love. It is a ring formed by connecting $N$ delicate rings and one special souvenir, as shown below. The heart symbol in the picture is one kind of special souvenir (it is said that zyg specially asked someone to customize it for Valentine’s Day in 2012). Each ring above is itself a ring made of $M$ magnetic special colored spherical objects. You may think that these so-called rings look more like small necklaces.

The picture below shows one feasible design. The left picture describes a single ring, and the right picture describes the whole necklace.

Here, the magnetic special colored spherical objects have only $R$ possible colors, denoted by $1$ to $R$. If one ring can become identical to another ring by rotating it clockwise or counterclockwise, then these two rings are considered the same.

For a Necklace of Love, any two adjacent rings must be different. Also, the two rings on the left and right of the special souvenir must be different.

Now given $N$, $M$, and $R$, determine how many different Necklaces of Love there are.

Note:

1. Different insertion positions of the special souvenir may produce different Necklaces of Love.
2. Here we only consider whether they are the same under rotation, and we do not consider flipping. This applies both to each ring and to the whole necklace.

Input Format

One line with three positive integers: $N$, $M$, and $R$.

Output Format

One line, the number of different Necklaces of Love. You only need to output the answer modulo $3214567$.

10 5 4

1398595

Hint

For $30\%$ of the testdata, $2\leq N \leq 10^3$, $M \leq 3 \times 10^2$, $R \leq 10^2$.

For $60\%$ of the testdata, $2\leq N \leq 3 \times 10^4$, $M \leq 2 \times 10^3$, $R \leq 10^5$.

For $80\%$ of the testdata, $2\leq N \leq 10^7$, $M \leq 10^6$, $R \leq 10^6$.

For $100\%$ of the testdata, $2\leq N \leq 10^{15}$, $M \leq 10^9$, $R \leq 10^6$.

Translated by ChatGPT 5