← 返回题目

题库练习 Grid Path

← 上一题下一题 →

A16516 | $Grid Path$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给定一个有 $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$ 取模的结果。

输入输出样例

输入 #1

2 2 100

输出 #1

输入 #2

1 5 777

输出 #2

输入 #3

5 3 998244353

输出 #3

输入 #4

100000000 150 1000000000

输出 #4

89058885

C++ 编辑器

输入

输出