题目背景

此题时限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    同上        同上    同上