661. Count Submatrices With All Ones

Given a binary matrix mat, return the number of submatrices (contiguous rectangular blocks) that contain only 1s. The input is JSON {mat}.

Input: JSON {mat}.

Output: Integer — the count of all-ones submatrices.

Examples

Example 1

Input: {"mat":[[1,0,1],[1,1,0],[1,1,0]]}
Output: 13
Explanation: Thirteen all-ones submatrices.

Example 2

Input: {"mat":[[0,1,1,0],[0,1,1,1],[1,1,1,0]]}
Output: 24
Explanation: Twenty-four such submatrices.

Example 3

Input: {"mat":[[1]]}
Output: 1
Explanation: One cell.