Count Regions With Sum Divisible by K

You are given an m x n grid of integers grid and a positive integer k. A region is a maximal group of positive cells that are 4-directionally connected (horizontally or vertically); a cell with value 0 is empty and belongs to no region.

The total of a region is the sum of the values of all its cells.

Return the number of regions whose total is divisible by k.

Examples

Example 1

Input: grid = [[0,2,1,0,0],[0,5,0,0,5],[0,0,1,0,0],[0,1,4,7,0],[0,2,0,0,8]], k = 5
Output: 2
Explanation: The grid has four regions. Two of them, with totals 15 and 5, are divisible by 5; the other two, both with total 8, are not.

Example 2

Input: grid = [[3,0,3,0],[0,3,0,3],[3,0,3,0]], k = 3
Output: 6
Explanation: The grid has six one-cell regions, each holding the value 3, so every region's total is divisible by 3.