case1: psum = MK
case 2 psum[j] - psum[i] == PK ==> psump[i] = MK + a psum[j] = N*K + a, therefore psum[j]- psm[i] = (N-M)K = PK

class Solution:
    def subarraysDivByK(self, A: List[int], K: int) -> int:
        # time O(N) space O(min(K,N))
        cnt = rsum = 0
        # to handle cases where psum is M*K
        d = {0:1}
        size = len(A)
        for i in range(size):
            rsum = (rsum + A[i]) % K 
            if rsum in d:
                # why not cnt + 1 ? 
                # there is d[rsum] set i ,j combinations so that A[i]+A[i+1]+..A[j] = n*K
                cnt += d[rsum]
                d[rsum] += 1
            else:
                d[rsum] = 1
        return cnt