5.计数问题

题目描述

有个无穷大的$m$维空间，一开始你在$(0,0,\cdots,0)$位置，每次你会等概率随机地往$2m$个方向走一步，即第$1$维加一或者减一，第$2$维加一或者减一……

请问走了$n$步之后，你能经过的不同位置个数的期望。

比如$(0,0) \to (0,1) \to (1,1) \to (1,0) \to (0,0)$这样的路径，你经过的位置是$(0,0)$，$(0,1)$，$(1,1)$，$(1,0)$。请输出期望乘上$(2m)^n$之后，对$mod$取模的结果。

输入格式

一行三个正整数$n$，$m$，$mod$。

输出格式

一行一个整数表示答案。

数据范围与提示

• 对于$10\%$的数据，$n \leq 5$；
• 对于另外$20\%$的数据，$m = 1$；
• 对于另外$20\%$的数据，$n \leq 50$，$m = 2$；
• 对于另外$20\%$的数据，$m = 2$；
• 对于$100\%$的数据，$1 \leq n \leq 2000$，$1 \leq m \leq 10$，$1 \leq mod \leq 10^{9}+7$。

样例

4 2 123456789

1068

30 2 1000000000

842235648

50 5 876543210

519048580