#P6839. 喵喵国的游走
喵喵国的游走
喵喵国的游走
题目描述
喵喵国是一个无限大的 维整数格点空间。犬犬从原点 出发,每一步等概率地选择 个方向之一:选择一个坐标,将它增加 或减少 。
走完 步后,求犬犬经过的不同位置的数量的期望 。起点也计入经过的位置,同一位置被多次经过只计一次。
例如,路径 经过了 个不同位置。
为避免分数,输出 。这个乘积是整数,模数不保证为质数。
输入格式
输入三个正整数 。
输出格式
输出一个整数,表示 。
样例输入 1
4 2 123456789
样例输出 1
1068
样例输入 2
30 2 1000000000
样例输出 2
842235648
样例输入 3
50 5 876543210
样例输出 3
519048580
数据范围
- 对于 的数据,。
- 另外 的数据,。
- 另外 的数据, 且 。
- 另外 的数据,。
- 对于所有数据,,,。
三个样例应分别独立运行,每次只输入一组数据。