Sum of Empowered Guardian Powers

In Hell, there are \(K\) guardians, each possessing an unknown ability value \(a_i\). The only known fact is that the sum of all ability values is \(N\), i.e., \(a_1+a_2+\cdots+a_K=N\). However, in Hell the guardians' powers are enhanced such that the effective power of a guardian is \(a_i^M\).

For every possible nonnegative integer solution \((a_1, a_2, \dots, a_K)\) satisfying \(a_1+a_2+\cdots+a_K=N\), let the power of that combination be defined as

[ \text{power} = \sum_{i=1}^{K} a_i^M, ]

Your task is to compute the sum of the power values over all possible combinations. By symmetry, note that this sum can be written as:

[ S = K \times \sum_{x=0}^{N} x^M \binom{N-x+K-2}{K-2}, ]

where \(\binom{n}{r}\) denotes the binomial coefficient. (Note: When \(K = 1\), there is exactly one guardian and only one possibility, so the answer is \(N^M\).)

inputFormat

The input consists of three space-separated integers: \(N\), \(M\), and \(K\).

outputFormat

Output a single integer representing the sum of the effective powers for all valid combinations.

sample

3 2 2

28