Problem Link : https://www.codechef.com/ENFE2020/problems/ECFEB207

Problem : Chef bought a rectangular checkered board of size N rows and M colums and color pens of P different colors. He randomly painted each cell with any of the P colors. When he was done painting all the cells, he noticed something very interesting property. For any vertical line that divides the board into two non-empty boards, the number of distinct colors in both the parts was the same.

Now, chef wonders in how many ways can he color the board using only the colors available such that this interesting property holds.

1≤N,M≤1000 1≤P≤10^6

Output : print the answer to the problem modulo 1000000007.

E.g. INPUT : 2 2 2 OUTPUT: 8

My Approach: I think, we can decide some colours which are to be arranged in the first column, and then each of the selected colour should be present in the last column at least once in any order , and the rest of the (N) X (N-2) matrix can have any distribution with these selected colours, because now,no matter wherever we draw a vertical line , number of distinct colours in the two parts will be same…I couldn’t implement it. Can anyone please let me know, if this approach is correct and how can I implement it. Or suggest some better approach…