为您提供一个网格,其中包含 $$$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