#P880. 【TYVJ1650】涂抹果酱

【TYVJ1650】涂抹果酱

【问题描述】

Tyvj两周年庆典要到了,Sam想为Tyvj做一个大蛋糕。蛋糕俯视图是一个N* M的矩形,它被划分成N* M个边长为1*1的小正方形区域。(可以把蛋糕当成N行M列的矩阵)蛋糕很快做好了,但光秃秃的蛋糕…肯定不好看!所以,Sam要在蛋糕的上表面涂抹果酱。果酱有三种,分别是红果酱、绿果酱、蓝果酱,三种果酱的编号分别为1,2,3。为了保证蛋糕的视觉效果,Admin下达了死命令:相邻的区域严禁使用同种果酱。但…Sam在接到这条命令之前,已经涂好了蛋糕第K行的果酱,且无法修改。

现在,Sam想知道,能令Admin满意的涂果酱方案有多少种(mod 10^6)。若不存在这种方案,请输出0

【输入格式】

输入共三行。

第一行:N M

第二行:K

第三行:M 个整数,表示第K 行的方案

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

【输出格式】

共一行:可行的方案总数.

【输入样例】

2 2
1
2 3

【输出样例】

3

【样例解释】

第一行的 2 3 是固定的,合理的果酱涂抹方案共3种:

--方案1--

2 3

1 2

--方案2--

2 3

3 1

--方案3--

2 3

3 2

【数据范围】

对于30%的数据,1<=N*M<=20

对于60%的数据,1<=N<=1000,1<=M<=3

对于100%的数据,1<=N<=10000,1<=M<=5