← 返回题目列表

Codeforces · 2204/G

G. 网格路径

中文机器翻译题面 查看原题

为您提供一个网格,其中包含 $$$n$$$ 行(从上到下编号从 $$$1$$$ 到 $$$n$$$)和 $$$m$$$ 列(从左到右编号从 $$$1$$$ 到 $$$m$$$)。您正在控制最初位于单元格 $$$(1, 1)$$$ 中的芯片。一步操作中,筹码可以向左、向右或向下移动(如果当前单元格是 $$$(x, y)$$$,则可以转到 $$$(x, y - 1)$$$、$$$(x, y + 1)$$$ 或 $$$(x + 1, y)$$$)。芯片不能离开网格。

你可以进行任意次数的移动(可能为零)。让我们定义 路径 芯片的 作为它至少访问一次的单元集。注意访问单元格的顺序 没有 很重要。

您的任务是计算可能路径的数量。由于答案可能很大,因此打印它对 $$$mod$$$ 取模。

输入

唯一的一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$mod$$$ ($$$1 \le n \le 10^8$$$; $$$1 \le m \le 150$$$; $$$2 \le mod \le 10^9$$$)。

输出

打印一个整数——可能路径的数量,以 $$$mod$$$ 为模。

示例

输入
复制

2 2 100

输出
复制

7

输入
复制

1 5 777

输出
复制

5

输入
复制

5 3 998244353

输出
复制

1695

输入
复制

100000000 150 1000000000

输出
复制

89058885