Problem Link : Here

Problem Statement:

You are given a grid of size M x N, where each square is colored with some random color among K colors with each having equal probability.

A Good Rectangle is defined as one where all squares lying on the inner border are of the same color.

What is the expected number of Good Rectangles in the given grid.

Constraints 1 <= N <= 10^5 1 <= M <= 10^5 1 <= K <= 10^5

Most of the AC codes i saw was some direct Formula in form of AGP or some other reduction. So if any one can Give me brief logical reduction to the formula, that would be great!