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.

-----Input-----

- 
First Line contains M, N, K

-----Output-----
A single value rounded off to the nearest Integer corresponding to the required answer.

-----Constraints-----
-  1 <= N <= 105 
-  1 <= M <= 105 
-  1 <= K <= 105 

-----Example-----
Input:
1 3 1
Output:
6

Difficulty: interview

Starter code:

Solutions:
def for1(M,k):
 ret = 0.0
 x = k*k+0.0
 z=x
 for m in range(1,M):
  ret+=(M-m)/x
  x*=z
 return ret 
  
def for2(M,k):
 ret = 0.0
 x = k+0.0
 for m in range(1,M):
  ret+=(M-m)/x
  
  x*=k
 return ret 
  
def ans(M,N,K):

 return int(round(M*N+M*for2(N,K)+N*for2(M,K)+K*for1(M,K)*for1(N,K),0))
M,N,K = list(map(int,input().split()))
print(ans(M,N,K)) 


n, m, k = list(map(int, input().split()))

if k == 1:
 x, y = 0, 0
 for p in range(2, n + 1):
  x += (n - p + 1)
 for p in range(2, m + 1):
  y += (m - p + 1)
 ans = x * y
 x = 0
 for p in range(1, n + 1):
  x += (n - p + 1)
 y = 0
 for p in range(1, m + 1):
  y += (m - p + 1)
 ans += m * x
 ans += n * y
 ans -= n * m
 print(ans)
else:
 x, y = 0.0, 0.0
 q = 1.0
 for p in range(2, n + 1):
  q /= k * k
  x += (n - p + 1) * q
 for p in range(2, m + 1):
  q /= k * k
  y += (m - p + 1) * q
 ans = k * x * y
 x = 0.0
 q = 1.0
 for p in range(1, n + 1):
  x += (n - p + 1) * q
  q /= k
 y = 0.0
 q = 1.0
 for p in range(1, m + 1):
  y += (m - p + 1) * q
  q /= k
 ans += m * x
 ans += n * y
 ans -= n * m
 ans += 1e-9
 # print ans
 print("%.0f" % ans)