There are n*m matrix (n,m<=1000) each element in the matrix are between 1 and 1e9 Count number of all rectangle in matrix that contain all the same element

how to solve this? I have been thinking for 2 days. Thank you very much.

Example:

Input:

2 3

1 1 2

1 1 2

output : 12