P15999 [ICPC 2020 NAC] Grid Guardian

爱丽丝有一个 $n \times m$ 的网格和一个 $2 \times 2$ 的方块。她希望将她的方块放入网格中。放置时必须使方块与坐标轴对齐，并且恰好覆盖 $4$ 个格子。 鲍勃想阻止爱丽丝这样做。为此，他在某些格子中放置障碍物。在鲍勃放置障碍物之后，网格中的所有 $2 \times 2$ 子网格都应该至少包含一个障碍物。鲍勃希望最小化他放置障碍物的格子数量。 请帮助鲍勃统计在放置最少障碍物的前提下，他有多少种放置方式。输出这个数量对素数 $p$ 取模的结果。注意，答案不是最少障碍物的数量，而是鲍勃在放置最少障碍物时的方案数。例如，对于 $2 \times 2$ 的网格（即 $n = m = 2$），鲍勃只需要放置 $1$ 个障碍物，但放置的方式有 $4$ 种，因此这种情况下的答案为 $4$。

输入仅一行，包含三个空格分隔的整数 $n$（$2 \le n \le 25$）、$m$（$2 \le m \le 10^3$）和 $p$（$10^8 \le p \le 10^9 + 7$，$p$ 是素数），其中爱丽丝的网格大小为 $n \times m$，$p$ 是一个大素数模数。

输出一个整数，表示鲍勃在 $n \times m$ 网格中放置最少障碍物以阻止爱丽丝放置她的 $2 \times 2$ 方块的方案数。由于答案可能很大，请输出它对 $p$ 取模的结果。

翻译由 DeepSeek V3.2 完成