Count Square Submatrices

Given a two-dimensional list of integers matrix containing 1s and 0s, return the total number of square submatrices with all 1 s.

Constraints

• n, m ≤ 250 where n and m are the number of rows and columns in matrix.

https://binarysearch.com/problems/Count-Square-Submatrices

Examples

Example 1

Input

• matrix =

[[1,1,0],
 [1,1,0]]

Output

• answer = 5

Explanation

There’s 4 of 1 × 1 squares and 1 2 × 2 square.

Solution