P2435 Coloring

The time limit for this problem is 2 s.

There is an $n$-row, $m$-column grid graph. You need to color each point with one of $k$ colors so that no two adjacent points have the same color. Given the colorings of the first row and the last row, find the total number of valid colorings. The answer is taken modulo $376544743$.

The first line contains three integers $n,m,k$. The second line contains $m$ integers, the coloring of the first row, where each color is represented by $0\sim k-1$. The third line contains $m$ integers, the coloring of the last row, where each color is represented by $0\sim k-1$.

Output a single integer, the answer. The answer is taken modulo $376544743$.

### Sample Explanation #### Scheme 1 ```plain 1 0 0 1 1 0 ``` #### Scheme 2 ```plain 1 0 0 2 1 0 ``` #### Scheme 3 ```plain 1 0 2 1 1 0 ``` ### Constraints | Test point ID | $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$ | For $100\%$ of the testdata, $n,m,k \ge 1$. Please note that the values of $\bm{n,m,k}$ do not simultaneously reach their maximum constraints. Translated by ChatGPT 5