Lattice Coloring Count

You are given an n by m grid. Each cell in the grid must be colored with one of k colors. Two cells are considered adjacent if they share a common side, and adjacent cells must not be colored the same.

The colors of the first and last rows are fixed. Your task is to count the number of ways to color the remaining rows such that the entire grid satisfies the adjacent cell constraint. Since the answer can be very large, output it modulo \(376544743\).

Note: It is guaranteed that the fixed rows themselves do not violate the adjacent cell constraints.

inputFormat

The first line contains three integers \(n\), \(m\), and \(k\) where \(n\) is the number of rows, \(m\) is the number of columns and \(k\) is the number of available colors.

The second line contains \(m\) space-separated integers representing the colors of the first row.

The third line contains \(m\) space-separated integers representing the colors of the last row.

All colors are in the range \(1\) to \(k\).

outputFormat

Output one integer, the number of valid colorings of the grid modulo \(376544743\).

sample

2 3 3
1 2 3
2 3 1

1