#P2435. 染色

染色

题目背景

此题时限2s

此题时限2s

此题时限2s

题目描述

有一个 n 行 m 列的格点图,你需要给每个点上染上 k 种颜色中的一种,要求没有两个相邻点颜色相同。给定第一行与最后一行的染色,试求总染色方案数。

输入格式

第一行三个整数 n,m,k。

第二行 m 个整数,第一行的染色方案,用 0~k-1 表示每种颜色。

第三行 m 个整数,最后一行的染色方案,用 0~k-1 表示每种颜色。

输出格式

一个整数,表示答案,对 376544743 取模。

3 2 3
1 0
1 0
3

提示

样例解释,三种方案:

1 0| 1 0| 1 0 0 1| 0 2| 2 1 1 0| 1 0| 1 0

no    n<=         m<=     k=
1     5         5     2
2     10^7     100000    2
3     20         3     3
4     50        同上    同上
5     100         6    同上
6    同上        同上    同上
7     50         4     4
8    同上        同上    同上
9     100         8    同上
10    同上        同上    同上