Number of different sequences in a matrix of $N{\times} M$ Consider all matrices with $N$ rows (numbered $1$ through $N$) and $M$ columns (numbered $1$ through $M$) containing only integers between $1$ and $K $(inclusive). For each such matrix , say $A$, let’s form a sequence $L_{\mathrm{1}},L_{\mathrm{2}},…,L_{\mathrm{N+M}}$:
For each $i$ ($1≤i≤N$), $L_{\mathrm{i}}$ is the maximum of all elements in the $i^{\mathrm{th}}$ row of $A$. Lets call these $N$ elements as sequence $B$.
For each $i$ ($1≤i≤M$), $L_{\mathrm{N+i}}$ is the maximum of all elements in the $i^{\mathrm{th}}$  column of $A$. Let's call these $M$ elements as sequence $C$.
Find the number of different sequences formed in this way.  
Example: When $N=2$ , $M=2$ & $K=2$ , the number of sequences are $10$.
The 10 sequences are :
$(0,0,0,0), (0,1,0,1), (0,1,1,0), (1,0,0,1), (1,0,1,0), (1,1,1,0), (1,0,1,1), (0,1,1,1), (1,1,0,1)$  and  $(1,1,1,1).$
I haven't found a way to prove that the number of sequences is a polynomial of degree $N+M-1$. 
A detailed proof and explaining the intuition behind it would be really appreciated.    
This is the original Problem link
 A: So, the solution is $$\sum_{i=0}^{K-1} ((i+1)^M - i^M)((i+1)^N - i^N)$$
For the intuition part,
Assume Li is the maximum of L1, L2.....LN. Now Li should be the maximum of LN+1, LN+2.....LN+M.  
Short proof for this claim - Assume this is not true, then there exists an element in LN+1, LN+2.....LN+M which is greater than Li then it must appear in any of the row. But, it doesn't, therefore it produces a contradiction. 
Now, if $L_i$ is the maximum element for both the part of the sequence as their maximum. So, numbers of distinct sequences for a row if $L_i$ is the maximum is $L_i^N - (L_i-1)^N$  which equals to placing every element from $0$ to $L_i$ at every position and then removing sequence when the element $L_i$ doesn't appear.
Example: For n = 3 and $L_i$ = 2
Possible sequences $(0, 0, 0),  (0, 0, 1),  (0, 1, 0),  (0, 1, 1),  (1, 0, 0),  (1, 0, 1),  (1, 1, 0),  (1, 1, 1)$ 
Valid sequences $(0, 0, 1),  (0, 1, 0),  (0, 1, 1),  (1, 0, 0),  (1, 0, 1),  (1, 1, 0),  (1, 1, 1)$
and counts $=2^3-(2-1)^3$ 
Now, put $0$ in every entry except for the column corresponding to the $L_i$. Now the matrix is valid as long as there exists the maximum element in it. So, every sequence can be formed from the column as long as that contains the $L_i$. So the same formula applies. And count is $L_i^M - (L_i-1)^M$. As we have used every possible sequence, we do not undercount by filling other entries as 0. You can prove there is no other possible sequence.
Now, we iterate over every possible maximum which is $1$ to $k-1$. Hence follows the summation.  
First Test Case
For N=M=K=2
$$((0+1)^2 - 0^2)((0+1)^2 - 0^2))+((1+1)^2 - 1^2))((1+1)^2 - 1^2)) = 10$$
Second Test case
For N=2, M=3, K=2
$$((0+1)^3 - 0^3)((0+1)^2 - 0^2))+((1+1)^3 - 1^3))((1+1)^2 - 1^2)) = 22$$ 
