We are given a N*M grid, print the number of rectangles in it.

Examples:

Input : N = 2, M = 2

Output : 9

There are 4 rectangles of size 1 x 1.

There are 2 rectangles of size 1 x 2

There are 2 rectangles of size 2 x 1

There is one rectangle of size 2 x 2.

Input : N = 5, M = 4

Output : 150

Input : N = 4, M = 3

Output: 60

Let us derive a formula for number of rectangles.

If the grid is 1×1, there is 1 rectangle.

If the grid is 2×1, there will be 2 + 1 = 3 rectangles

If it grid is 3×1, there will be 3 + 2 + 1 = 6 rectangles.

we can say that for N*1 there will be N + (N-1) + (n-2) … + 1 = (N)(N+1)/2 rectangles
If we add one more column to N×1, firstly we will have as many rectangles in the 2nd column as the first,
and then we have that same number of 2×M rectangles.
So N×2 = 3 (N)(N+1)/2
After deducing this we can say
For N*M we’ll have (M)(M+1)/2 (N)(N+1)/2 =

**M(M+1)(N)(N+1)/4**

So the formula for total rectangles will be M(M+1)(N)(N+1)/4

.

**Combinatorial Logic:**

N*M grid can be represented as (N+1) vertical lines and (M+1) horizontal lines.

In a rectangle, we need two distinct horizontal and two distinct verticals.

So going by the logic of Combinatorial Mathematics we can choose 2 vertical lines and 2 horizontal lines to form a rectangle. And total number of these combinations is the number of rectangles possible in the grid.

Total Number of Rectangles in N*M grid: N+1C2 * M+1C2 = *(N(N+1)/2!)*(M*(M+1)/2!)** =

***

*N*(N+1)*M*(M+1)/4`// JAVA Code to count number of`

`// rectangles in N*M grid`

`import`

`java.util.*;`

`class`

`GFG {`

` `

` `

`public`

`static`

`long`

`rectCount(`

`int`

`n, `

`int`

`m)`

` `

`{`

` `

`return`

`(m * n * (n + `

`1`

`) * (m + `

`1`

`)) / `

`4`

`;`

` `

`}`

` `

` `

`/* Driver program to test above function */`

` `

`public`

`static`

`void`

`main(String[] args)`

` `

`{`

` `

`int`

`n = `

`5`

`, m = `

`4`

`;`

` `

`System.out.println(rectCount(n, m));`

` `

`}`

`}`

**Output:**

150