Problem Description

Xiaoshan has $n$ identical elements. He wants to divide these $n$ elements into $m$ piles. Obviously, there are many ways to do this. For each division, let $a_i$ be the number of elements in the $i$-th pile, $b_i=i!\times a_i$ (where $i!$ denotes the factorial of $i$), and $c=\sum\limits_{i=1}^m b_i$. Xiaoshan's elemental power is defined as the sum of the values of $c$ over all divisions. Xiaoshan wants to know what his elemental power is. Since the answer may be very large, output the final answer modulo $p$ (it is guaranteed that $p$ is a prime number).

Input Format

One line with three integers $n, m, p$, with meanings given in the Description.

Output Format

Output one number representing Xiaoshan's elemental power.

3 2 37

18

Hint

Sample Explanation

The ways to divide $3$ elements into $2$ piles are:

1. 0 3
2. 1 2
3. 2 1
4. 3 0

Xiaoshan's elemental power is: $(1!\times0+2!\times3)+(1!\times1+2!\times2)+(1!\times2+2!\times1)+(1!\times3+2!\times0)=18$.

Constraints

For $100\%$ of the testdata, $1\le n,m\le10^6$, $1\le p\le10^7$.

Translated by ChatGPT 5