染色
题目背景
此题时限2s
此题时限2s
此题时限2s
题目描述
有一个 $n$ 行 $m$ 列的格点图，你需要给每个点上染上 $k$ 种颜色中的一种，要求没有两个相邻点颜色相同。给定第一行与最后一行的染色，试求总染色方案数。
输入输出格式
输入格式
第一行三个整数 $n,m,k$。
第二行 $m$ 个整数，第一行的染色方案，用 $0\sim k-1$ 表示每种颜色。
第三行 $m$ 个整数，最后一行的染色方案，用 $0\sim k-1$ 表示每种颜色。
输出格式
一个整数，表示答案，对 $376544743$ 取模。
输入输出样例
输入样例 #1
3 2 3
1 0
1 0输出样例 #1
3
说明
样例解释，三种方案：
1 0| 1 0| 1 0
0 1| 0 2| 2 1
1 0| 1 0| 1 0
| 测试点编号 | $n$ | $m$ | $k$ |
| :----------: | :----------: | :----------: | :----------: |
| $1$ | $≤5$ | $≤5$ | $≤2$ |
| $2$ | $≤10^7$ | $≤10^5$ | $≤2$ |
| $3$ | $≤20$ | $≤3$ | $≤3$ |
| $4$ | $≤50$ | $≤3$ | $≤3$ |
| $5-6$ | $≤100$ | $≤6$ | $≤3$ |
| $7-8$ | $≤50$ | $≤4$ | $≤4$ |
| $9-10$ | $≤100$ | $≤8$ | $≤4$ |