CF2204G.Grid Path

You are given a grid with $n$ rows (numbered from $1$ to $n$ from top to bottom) and $m$ columns (numbered from $1$ to $m$ from left to right). You are controlling a chip that is initially in the cell $(1, 1)$. In one move, the chip can move left, right, or down (if the current cell is $(x, y)$, it can go to $(x, y - 1)$, $(x, y + 1)$, or $(x + 1, y)$). The chip cannot leave the grid.

You can make any number of moves (possibly zero). Let's define the path of a chip as the set of cells it visits at least once. Note that the order of visited cells doesn't matter.

Your task is to calculate the number of possible paths. Since the answer might be large, print it modulo $mod$.

给你一个 $n$ 行（从上到下编号为 $1$ 到 $n$）和 $m$ 列（从左到右编号为 $1$ 到 $m$）的网格。你控制一个芯片，它初始位于单元格 $(1, 1)$。在一次移动中，芯片可以向左、向右或向下移动（若当前单元格为 $(x, y)$，则它可以移动到 $(x, y - 1)$、$(x, y + 1)$ 或 $(x + 1, y)$）。芯片不能移出网格边界。

你可以进行任意次数（包括零次）的移动。我们定义芯片的路径为它至少访问过一次的所有单元格构成的集合（注意：访问顺序无关紧要）。

你的任务是计算可能的路径总数。由于答案可能很大，请对 $mod$ 取模后输出。

The only line contains three integers $n$, $m$, and $mod$ ($1 \le n \le 10^8$; $1 \le m \le 150$; $2 \le mod \le 10^9$).

唯一一行包含三个整数 $n$、$m$ 和 $mod$（$1 \le n \le 10^8$；$1 \le m \le 150$；$2 \le mod \le 10^9$）。

Print a single integer — the number of possible paths, taken modulo $mod$.

输出一个整数——可能的路径数量对 $mod$ 取模的结果。