Count sub | function to count all sub - arrays divisible by k ; create auxiliary hash array to count frequency of remainders ; Traverse original array and compute cumulative sum take remainder of this current cumulative sum and increase count by 1 for this remainder in mod array ; as the sum can be negative , taking modulo twice ; Initialize result ; Traverse mod ; If there are more than one prefix subarrays with a particular mod value . ; add the subarrays starting from the arr [ i ] which are divisible by k itself ; function to count all sub - matrices having sum divisible by the value 'k   ; Variable to store the final output ; Set the left column ; Set the right column for the left column set by outer loop ; Calculate sum between current left and right for every row 'i   ; Count number of subarrays in temp having sum divisible by ' k ' and then add it to 'tot_count   ; required count of sub - matrices having sum divisible by 'k   ; Driver Code
def subCount ( arr , n , k ) : NEW_LINE INDENT mod = [ 0 ] * k ; NEW_LINE cumSum = 0 ; NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT cumSum = cumSum + arr [ i ] ; NEW_LINE mod [ ( ( cumSum % k ) + k ) % k ] = mod [ ( ( cumSum % k ) + k ) % k ] + 1 ; NEW_LINE DEDENT result = 0 ; NEW_LINE for i in range ( 0 , k ) : NEW_LINE INDENT if ( mod [ i ] > 1 ) : NEW_LINE INDENT result = result + int ( ( mod [ i ] * ( mod [ i ] - 1 ) ) / 2 ) ; NEW_LINE DEDENT DEDENT result = result + mod [ 0 ] ; NEW_LINE return result ; NEW_LINE DEDENT def countSubmatrix ( mat , n , k ) : NEW_LINE INDENT tot_count = 0 ; NEW_LINE temp = [ 0 ] * n ; NEW_LINE for left in range ( 0 , n - 1 ) : NEW_LINE INDENT for right in range ( left , n ) : NEW_LINE INDENT for i in range ( 0 , n ) : NEW_LINE INDENT temp [ i ] = ( temp [ i ] + mat [ i ] [ right ] ) ; NEW_LINE DEDENT tot_count = ( tot_count + subCount ( temp , n , k ) ) ; NEW_LINE DEDENT DEDENT return tot_count ; NEW_LINE DEDENT mat = [ [ 5 , - 1 , 6 ] , [ - 2 , 3 , 8 ] , [ 7 , 4 , - 9 ] ] ; NEW_LINE n = 3 ; NEW_LINE k = 4 ; NEW_LINE print ( " Count ▁ = ▁ { } " . format ( countSubmatrix ( mat , n , k ) ) ) ; NEW_LINE