#P7228. [2023省队模拟]染盘

    ID: 7062 传统题 1000ms 888MiB 尝试: 2 已通过: 2 难度: 8 上传者: 标签>CF2500提高+/省选-轮廓线 DP轮廓状态规范化对称性分析预计算转移滚动数组位压缩存储哈希表

[2023省队模拟]染盘

题目描述

将一个 n×mn\times m 的棋盘上的每个格子染成黑色或白色。要求所有黑色格子四连通,所有白色格子也四连通。问有多少种染色方案。

四连通是指只通过上下左右相邻的同色格子即可连通。棋盘上只有一种颜色的方案也计入答案。

输入格式

输入三个整数 n,m,pn,m,p。

输出格式

输出答案对 pp 取模的结果。

样例输入 1

2 2 998244353

样例输出 1

14

样例输入 2

3 3 998244353

样例输出 2

108

数据范围与约定

对于所有数据,1≤m≤81\le m\le8,1≤n⋅m≤1041\le n\cdot m\le10^4,2≤p≤1092\le p\le10^9,且 pp 是质数。

对于每个满足 1≤K<81\le K<8 的整数 KK,有一个价值 1010 分的子任务 m=Km=K。即通过 m≤Km\le K 的数据可以获得 10K10K 分。