背景

此题时限 2s。

题目描述

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

答案对 $376544743$ 取模。

输入格式

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

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

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

输出格式

一个整数，表示答案。

答案对 $376544743$ 取模。

3 2 3
1 0
1 0

3

提示

样例解释

方案 1

1 0
0 1
1 0

方案 2

1 0
0 2
1 0

方案 3

1 0
2 1
1 0

数据范围

对于 $100\%$ 的数据，$n,m,k \ge 1$。

请注意，$\bm{n,m,k}$ 的值没有同时达到最大数据范围。