P10380 "ALFR Round 1" D Xiaoshan's Elemental Power

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).

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

Output one number representing Xiaoshan's elemental power.

### 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 | Subtask | Score | Constraints | | :----------: | :----------: | :----------: | | $0$ | $20$ | $n,m\le5$ | | $1$ | $80$ | - | For $100\%$ of the testdata, $1\le n,m\le10^6$, $1\le p\le10^7$. Translated by ChatGPT 5