#488. 涂抹果酱

涂抹果酱

题目描述

Tyvj 两周年庆典要到了,Sam 想为 Tyvj 做一个大蛋糕。蛋糕俯视图是一个 N×M\red{N×M }的矩形,它被划分成N×M\red{ N×M }个边长为 1×1\red{1×1 }的小正方形区域(可以把蛋糕当成 N\red{N }M\red{M} 列的矩阵)。蛋糕很快做好了,但光秃秃的蛋糕肯定不好看!所以,Sam 要在蛋糕的上表面涂抹果酱。果酱有三种,分别是红果酱、绿果酱、蓝果酱,三种果酱的编号分别为 1,2,3\red{1,2,3}。为了保证蛋糕的视觉效果,Admin 下达了死命令:相邻的区域严禁使用同种果酱。但 Sam 在接到这条命令之前,已经涂好了蛋糕第 K\red{K }行的果酱,且无法修改。 现在 Sam 想知道:能令 Admin 满意的涂果酱方案有多少种。请输出方案数mod106\red{ \bmod 10^6}。若不存在满足条件的方案,请输出 0\red{0}

输入格式

输入共三行。

第一行:N,M\red{N, M}

第二行:K\red{K}

第三行:M\red{M} 个整数,表示第 K\red{K} 行的方案。

字母的详细含义见题目描述,其他参见样例。

输出格式

输出仅一行,为可行的方案总数。

样例

输入样例

2 2
1
2 3

输出样例

3
方案一 方案二 方案三
2 3\red{\texttt{2 3}} 2 3\red{\texttt{2\ 3}} 2 3\red{\texttt{2 3}}
1 2\red{\texttt{1 2}} 3 1\red{\texttt{3 1}} 3 2\red{\texttt{3 2} }

提示

对于 30%\red{30\% }的数据,1N×M20\red{1≤N×M≤20}

对于 60%\red{60\% }的数据,1N1000,1M3\red{1≤N≤1000,1≤M≤3}

对于 100%\red{100\%} 的数据,1N10000,1M5\red{1≤N≤10000,1≤M≤5}