#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