题目背景

此题时限2s

此题时限2s

此题时限2s

题目描述

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

输入格式

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

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

第三行 $m$ 个整数，最后一行的染色方案，用 $0\sim 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