[AdditionalFile6385.zip](file://AdditionalFile6385.zip?type=additional_file)

#6385. 「ECNU Coder 2018」棋盘染色

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

把一个 $n \times m$ 的棋盘染成黑白两色，要求黑色的块全部四连通，白色的块也全部四连通。问有多少种方案？

四连通：一个格子与上、下、左、右四个方向的格子有连通。

输入格式

输入三个数 $n, m, p$。

输出格式

输出答案模 $p$。

样例 1

输入

2 2 998244353

输出

14

样例 2

输入

3 3 998244353

输出

108

数据范围与提示

$1 \le m \le 8$；$1 \le n \cdot m \le 10^4$；$2 \le p \le 10^9$；$p$ 是质数。