题目描述

小山有 $n$ 个相同的元素，他想将这 $n$ 个元素分为 $m$ 堆，显然有很多种分法。对于每种分法，定义 $a_i$ 为第 $i$ 堆的元素数量，$b_i=i!\times a_i$（其中 $i!$ 表示 $i$ 的阶乘），以及 $c=\sum\limits_{i=1}^mb_i$。而小山的元力为所有分法的 $c$ 值之和。小山想知道他的元力是多少，由于答案可能很大，所以最终答案应对 $p$ 取模（保证 $p$ 为质数）。

输入格式

一行三个整数 $n,m,p$，含义见题目描述。

输出格式

一个数表示小山的元力。

3 2 37

18

提示

样例解释

将 $3$ 个元素分为 $2$ 堆的方案为：

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

小山的元力为：$(1!\times0+2!\times3)+(1!\times1+2!\times2)+(1!\times2+2!\times1)+(1!\times3+2!\times0)=18$。

数据范围

对于 $100\%$ 的数据，$1\le n,m\le10^6$，$1\le p\le10^7$。