The Love Necklace

In the folklore of the Jinxiang River, there is a beautiful story about two children, zyg and kzn. One day after a quarrel, zyg gifted kzn an exquisite love necklace. Although the truth of this tale has faded, our attention is captured by that magnificent necklace.

This necklace is formed by connecting N exquisite rings with a special commemorative memento. The memento (designed on Valentine’s Day 2012 at the request of zyg) is symbolized by a heart shape. Each ring is itself a circular arrangement of M special magnetic balls colored with one of R colors (represented by the integers from 1 to R). Two rings are considered identical if one can be rotated (clockwise or anticlockwise) to match the other (reflections are not considered).

The necklace must satisfy the following conditions:

• Any two rings that appear consecutively (i.e. adjacent in the circle) must be different.
• The two rings adjacent to the special memento (which can be inserted in any gap between rings) must also be different.

Note that a different insertion position for the memento results in a different necklace.

Task: Given N, M and R, count the number of different love necklaces.

Let the number of distinct rings (up to rotation) be \[ K = \frac{1}{M}\sum_{d|M} \varphi(d)\,R^{\frac{M}{d}}, \] where \(\varphi\) is Euler's totient function. Then the number of valid necklaces is given by \[ \text{Answer} = N \times \left[ (K-1)^N + (-1)^N (K-1) \right]. \]

inputFormat

The input consists of a single line containing three integers: N, M, and R, where N is the number of rings, M is the number of magnetic balls on each ring, and R is the number of available colors.

outputFormat

Output a single integer representing the total number of different love necklaces.

sample

1 1 1

0