The Power of Partitions

You are given three integers n, m and p, where p is a prime number. Consider all ways to partition n identical elements into m piles (some piles may be empty). For each partition, denote the number of elements in the i-th pile as \(a_i\) (for \(1 \le i \le m\)). Define \(b_i = i! \times a_i\) (where \(i!\) is the factorial of \(i\)) and \(c = \sum_{i=1}^{m} b_i\). The power of the configuration is defined as the sum of \(c\) over all possible partitions. Since the answer can be huge, output it modulo \(p\).

Note: A partition is a sequence \((a_1, a_2, \ldots, a_m)\) of nonnegative integers satisfying \(a_1+a_2+\cdots+a_m=n\).

Hint: By linearity, the answer can be computed as \(\frac{n \times T}{m} \times \sum_{i=1}^{m} i!\) modulo \(p\), where \(T = \binom{n+m-1}{m-1}\) is the total number of partitions.

inputFormat

The input consists of a single line containing three space-separated integers \(n\), \(m\), and \(p\) (with \(p\) being prime).

outputFormat

Output one integer: the power modulo \(p\).

sample

1 2 7

3