You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

输入格式

输入共三行。
第一行：$N, M$；
第二行：$K$；
第三行：$M$ 个整数，表示第 $K$ 行的方案。
字母的详细含义见题目描述，其他参见样例。

输出格式

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

样例

2 2
1
2 3

3

数据范围与提示

对于 30% 的数据，$1≤N×M≤20$；
对于 60% 的数据，$1≤N≤1000,1≤M≤3$；
对于 100% 的数据，$1≤N≤10000,1≤M≤5$。