小 A 同学在上绘画课。

课上，小 A 同学画出了一个 N \times M 的矩阵，矩阵的每个格子都将被涂上一种颜色。小 A 同学领到的涂料只有 3 种颜色，用数字 1,2,3 代表这 3 种不同的颜色，每个格子只能使用其中一种颜色上色。

小 A 为矩阵的第 C 行上好了颜色（其它行还未上色）。老师提出要求，请同学们在上色的时候，任意两个相邻的格子（上下左右四方向）不能使用同一种颜色。

请编程计算出，小 A 有多少种不同的上色方案。由于上色方案数可能非常多，最终请输出方案数 \mod 10^6 的结果。

第 1 行输入 N,M。

第 2 行输入整数 C。

第 3 行输入 M 个整数，代表第 C 行的上色方案。

按题意输出方案总数。

数据范围

对于 100\% 的数据 1≤N≤10^4,1≤M≤5。

样例解释

共三种可行方案:

方案一：

2 3
1 2

方案二：

2 3
3 1

方案三：

2 3
3 2

压状DP