题目背景

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

数据范围

测试点编号	$n$	$m$	$k$
$1$	$\le 5$		$\le 2$
$2$	$\le 10^7$	$\le 10^5$
$3$	$\le 20$	$\le 3$	$\le 3$
$4$	$\le 50$
$5 \sim 6$	$\le 100$	$\le 6$
$7 \sim 8$	$\le 50$	$\le 4$	$\le 4$
$9 \sim 10$	$\le 100$	$\le 8$

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

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