- Time limit: 2.00 s
- Memory limit: 512 MB
You are given an n \times m grid whose each square is either black or white.
Count the number of rectangles whose each corner square is black.
Input
The first input line contains two integer n and m: the size of the grid.
Then, there are n lines of length m that describe the grid. Each line consists of characters 0 (white) and 1 (black).
Output
Print the number of rectangles whose each corner square is black.
Constraints
- 1 \le n,m \le 3000
Example
Input:
3 4 0111 0011 0101
Output:
2