Let \((i, j)\) denote the square at the \(i\)-th row and \(j\)-th column.

If \(N=1\), the integer written on \((1, j)\) is \(B_j\). Thus, once the sequence \(B\) is set, the value \(A_1\) will be automatically determined. Therefore, the answer is \(K^M\).

If \(M=1\), by a similar argument, the answer is \(K^N\).

Now, let us assume \(N,M\geq 2\). Without loss of generality, we can assume \(A_1\) is the maximum among \(A_i\), and \(B_1\) is the minimum among \(B_i\). Then, the integer written on \((1, 1)\) needs to be between \(A_1\) and \(B_1\) (inclusive), so it is necessary that \(A_1 \leq B_1\).

On the other hand, we can prove that if \(A_1 \leq B_1\), there is a way to write integers that is consistent with the sequences. Actually, we can do so as follows:

• write \(A_1, A_2, B_1, B_2\) on \((1, 1), (2, 2), (2, 1), (1, 2)\), respectively;
• write \(A_3,\dots, A_N\) on \((3,1),\dots, (N,1)\), respectively;
• write \(B_3,\dots, A_M\) on \((1,3),\dots, (1,M)\), respectively;
• write \(A_i\) on each of the remaining squares in the \(i\)-th row.

By considering the case where the maximum value among \(A_i\) is fixed to \(x\), we can see that there are \(\sum_{x=1}^{K} (x^N-(x-1)^N)(K-x+1)^M\) such pairs of sequences.