当前没有测试数据。

发放奖金

题目描述

老板有$m$元，要给$n$名不同员工发奖金，每名员工的奖金数应当是非负整数，并且$m$元不一定要全部发完。

好奇的老板想知道，给定$n$和$m$，他有多少种发奖金的方案？这个答案很大，所以再给定一个$p$，最终的答案取模$p$的余数。

输入格式

第一行三个整数$n$，$m$，$p$。

输出格式

仅一行，一个整数表示最终的答案取模$p$的余数。

数据范围与提示

设$p = p_{1}^{c_{1}} p_{2}^{c_{2}} p_{3}^{c_{3}} \cdots p_{t}^{c_{t}}$，$p_{i}$为质数。

• 对于$20\%$的数据，$1 \leq n$，$m \leq 15$；
• 对于$40\%$的数据，$1 \leq n$，$m \leq 1000$，$p = 10007$；
• 对于$60\%$的数据，保证$t = 1$，$c_{i} = 1$，$p_{i}^{c_{i}} \leq 10^{5}$；
• 对于$80\%$的数据，$t \leq 2$，$c_{i} = 1$，$p_{i} \leq 10^{5}$；
• 对于$100\%$的数据，$1 \leq n$，$m \leq 10^{9}$，$1 \leq p_{i}^{c_{i}} \leq 10^{5}$，所有$p$不超过$2^{31}-1$。

样例

2 1 5

3