A decorative mosaic is an R by C grid; tile value g[i][j] is an integer color-weight (which may be negative). Given a target t, count how many non-empty axis-aligned subrectangles have a tile-weight sum of exactly t. Two subrectangles are different if their sets of tiles differ (that is, if any of their four boundaries differ).
Input format
Line 1: two integers R and C.
Next R lines: each has C space-separated integers (one grid row).
Next line: an integer t.
Output format
A single integer: the number of non-empty axis-aligned subrectangles whose sum equals t.
Constraints
- 1 <= R, C <= 60
- -10000 <= each tile value <= 10000
- -1000000000 <= t <= 1000000000