好的，我将这道题整理为清晰的题面格式，并补充样例解释、数据范围与时空限制：

---

题目描述

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

现在 Sam 想知道：能令 Admin 满意的涂果酱方案有多少种。请输出方案数 $\bmod 10^6$。若不存在满足条件的方案，请输出 $0$。

---

输入格式

输入共三行：

• 第一行：两个整数 $N, M$；
• 第二行：一个整数 $K$；
• 第三行：$M$ 个整数，表示第 $K$ 行的方案（每个整数为 $1,2,3$ 中的一个）。

---

输出格式

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

---

样例

样例输入

2 2
1
2 3

样例输出

3

样例说明

$N=2, M=2, K=1$，第 $1$ 行固定为 2 3。

要求相邻区域（上下左右）不能涂相同果酱。

第 $2$ 行可以涂的方案如下：

1. 2 3（与第 1 行完全相同，但上下相邻的格子不能相同？检查：第 1 列上下都是 2，相同，不允许，所以此方案无效） 需要重新检查：第 1 列上下都是 2（相同），违反条件，所以不能。 因此上面给出的方案表可能有误。我们重新计算：

第 1 行固定为：

2 3

第 2 行需要满足：

• 第 1 列不能为 2（因为上面是 2）
• 第 2 列不能为 3（因为上面是 3）
• 同一行左右不能相同

枚举第 2 行：

• (1,1)：不能是 2，可以是 1 或 3
• (1,2)：不能是 3，可以是 1 或 2

且左右不能相同。

枚举：

• 若选 (1,1)=1, (1,2)=1：左右相同，无效
• (1,1)=1, (1,2)=2：左右不同，且上下不同（1≠2, 2≠3），有效
• (1,1)=3, (1,2)=1：左右不同，且上下不同（3≠2, 1≠3），有效
• (1,1)=3, (1,2)=2：左右不同，且上下不同（3≠2, 2≠3），有效

所以第 2 行有 3 种方案，因此总方案数为 3。

原题给出的方案表是正确的（方案一：第2行 2 3 应为 1 2，方案二 2 3 应为 3 1，方案三 2 3 应为 3 2，表格中第1行固定为 2 3，第2行对应三种情况）。

---

数据范围

• 对于 $30\%$ 的数据，$1 \le N \times M \le 20$；
• 对于 $60\%$ 的数据，$1 \le N \le 1000, 1 \le M \le 3$；
• 对于 $100\%$ 的数据，$1 \le N \le 10000, 1 \le M \le 5$。

---

时空限制

• 时间：$1000 \text{ ms}$
• 内存：$524288 \text{ KB}$

---

提示
此题为 状态压缩 DP，但状态是三进制（$M \le 5$，三进制状态数最多 $3^5=243$，可以接受）。

状态表示：用一个 $M$ 位的三进制数表示一行的果酱涂法，每位 $0,1,2$ 对应果酱 $1,2,3$（注意转换时可能需要映射）。

条件：

1. 同一行内相邻位置不能相同（即三进制数的相邻位不能相等）；
2. 上下两行相同位置不能相同；
3. 第 $K$ 行固定为给定状态。

DP 设计： 设 $dp[i][s]$ 表示处理到第 $i$ 行，且该行状态为 $s$ 的方案数。

转移：

$$dp[i][s] = \sum_{s'} dp[i-1][s']$$

其中 $s'$ 是上一行的状态，且满足：

• $s$ 内部相邻位不同；
• $s'$ 内部相邻位不同；
• $s$ 和 $s'$ 对应位不相同。

初始化：

• 若 $i = K$，则 $dp[K][\text{fixed\_state}] = 1$，其他状态为 $0$；
• 若 $i \neq K$，则正常转移。

最终答案：

$$\text{ans} = \sum_{s} dp[N][s] \pmod{10^6}$$

注意：

• 需要预处理所有合法状态（相邻位不同）；
• 预处理状态间的兼容性（对应位不同）；
• 由于 $N$ 较大，需要滚动数组优化空间。

复杂度：$O(N \times |S|^2)$，$|S| \le 3^M \approx 243$，$N \le 10000$，大约 $10000 \times 243^2 \approx 5.9\times 10^8$ 可能超时，但实际合法状态数远小于 $243$（因为相邻不能相同），可以过。