A16516. Grid Path
编程题
省选/NOI-
知识点
题目描述
给定一个有 $n$ 行（从上到下编号为 $1$ 到 $n$）和 $m$ 列（从左到右编号为 $1$ 到 $m$）的网格。你控制一个最初位于格子 $(1, 1)$ 的芯片。每次移动，芯片可以向左、向右或向下移动（若当前格子为 $(x, y)$，则可以移动到 $(x, y-1)$、$(x, y+1)$ 或 $(x+1, y)$）。芯片不能离开网格。
你可以进行任意次移动（包括零次）。将芯片的**路径**定义为它至少访问一次的格子的集合。注意，访问格子的顺序**无关紧要**。
你的任务是计算可能的路径数量。由于答案可能很大，请将其对 $mod$ 取模后输出。
你可以进行任意次移动（包括零次）。将芯片的**路径**定义为它至少访问一次的格子的集合。注意，访问格子的顺序**无关紧要**。
你的任务是计算可能的路径数量。由于答案可能很大，请将其对 $mod$ 取模后输出。
输入格式
仅一行，包含三个整数 $n$、$m$ 和 $mod$（$1 \le n \le 10^8$；$1 \le m \le 150$；$2 \le mod \le 10^9$）。
输出格式
输出一个整数表示可能的路径数量对 $mod$ 取模的结果。
输入输出样例
输入 #1
2 2 100
输出 #1
7
输入 #2
1 5 777
输出 #2
5
输入 #3
5 3 998244353
输出 #3
1695
输入 #4
100000000 150 1000000000
输出 #4
89058885