P2435 染色

**此题时限 2s。**

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

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

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

### 样例解释 #### 方案 1 ```plain 1 0 0 1 1 0 ``` #### 方案 2 ```plain 1 0 0 2 1 0 ``` #### 方案 3 ```plain 1 0 2 1 1 0 ``` ### 数据范围 | 测试点编号 | $n$ | $m$ | $k$ | | :----------: | :----------: | :----------: | :----------: | | $1$ | $\le 5$ | $\le 5$ | $\le 2$ | | $2$ | $\le 10^7$ | $\le 10^5$ | $\le 2$ | | $3$ | $\le 20$ | $\le 3$ | $\le 3$ | | $4$ | $\le 50$ | $\le 3$ | $\le 3$ | | $5 \sim 6$ | $\le 100$ | $\le 6$ | $\le 3$ | | $7 \sim 8$ | $\le 50$ | $\le 4$ | $\le 4$ | | $9 \sim 10$ | $\le 100$ | $\le 8$ | $\le 4$ | 对于 $100\%$ 的数据，$n,m,k \ge 1$。 **请注意，$\bm{n,m,k}$ 的值没有同时达到最大数据范围。**