Description

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$.

Input Format

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 Format

Output a single integer, the answer.

The answer is taken modulo $376544743$.

3 2 3
1 0
1 0

3

Hint

Sample Explanation

Scheme 1

1 0
0 1
1 0

Scheme 2

1 0
0 2
1 0

Scheme 3

1 0
2 1
1 0

Constraints

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