Problem statement

https://binarysearch.com/problems/Squares-in-a-Grid/

Solution

We can notice that every square can be inscribed into some square with sides parallel to OX and OY. Moreover for square with side t, there can be (r-t)*(c-t) ways to choose this square and then t ways to incribe another square inside. Total answer is

\(\sum\limits_{t=1}^{\min(r,c)}(r-t)(c-t)t,\) which can be written in closed form, using sum of squares and sum of cubes formulae.

Complexity

It is O(1) for time and space.

Code

class Solution:
    def solve(self, r, c):
        x = min(r, c)
        return (x*(x+1)*(c*(6*r-4*x-2) - 2*r*(2*x+1) + 3*x*(x+1))//12) % (10**9 + 7)