You are given an array A of N positive and/or negative integers and a value K. The task is to find the count of all sub-arrays whose sum is divisible by K.
Example 1:
Input: N = 6, K = 5
       arr[] = {4, 5, 0, -2, -3, 1}
Output: 7
Explanation: There are 7 sub-arrays whose 
is divisible by K {4, 5, 0, -2, -3, 1}, {5}, 
{5, 0}, {5, 0, -2, -3}, {0}, {0, -2, -3} 
and {-2, -3}
Example 2:
Input: N = 6, K = 2
       arr[] = {2, 2, 2, 2, 2, 2}
Output: 21
Explanation: All subarray sums are 
divisible by 7
 
Your Task:
This is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function subCount() that takes array arr, integer N, and integer K as parameters and returns the desired output.
Expected Time Complexity: O(N+K).
Expected Auxiliary Space: O(K).
 
Constraints:
2 ≤ N ≤ 10^{5}

Difficulty: EASY
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N+K).
Expected Auxiliary Space: O(K).

Starter code:
class Solution:
    def subCount(self,arr, n, k):
        # Your code goes here

Solutions:
class Solution:

	def subCount(self, arr, n, k):
		hashmap = {}
		currSum = 0
		for i in range(n):
			currSum += arr[i]
			arr[i] = currSum
			arr[i] %= k
			hashmap[arr[i]] = hashmap.get(arr[i], 0) + 1
		ans = 0
		for x in hashmap.keys():
			y = hashmap[x]
			if x == 0:
				ans += y * (y + 1) // 2
			else:
				ans += y * (y - 1) // 2
		return ans


class Solution:

	def subCount(self, arr, n, k):
		mod = []
		for i in range(k + 1):
			mod.append(0)
		cumSum = 0
		for i in range(n):
			cumSum = cumSum + arr[i]
			mod[(cumSum % k + k) % k] = mod[(cumSum % k + k) % k] + 1
		result = 0
		for i in range(k):
			if mod[i] > 1:
				result = result + mod[i] * (mod[i] - 1) // 2
		result = result + mod[0]
		return result


from collections import defaultdict as dd

class Solution:

	def subCount(self, arr, n, k):
		store = dd(lambda : 0)
		store[0] = 1
		output = 0
		summa = 0
		for item in arr:
			summa = (summa + item) % k
			output += store[summa]
			store[summa] += 1
		return output


class Solution:

	def subCount(self, arr, n, k):
		count = [0] * k
		count[0] = 1
		prefix_sum = 0
		ans = 0
		for i in range(n):
			prefix_sum += arr[i]
			modulo = prefix_sum % k
			ans += count[modulo]
			count[modulo] += 1
		return ans


class Solution:

	def subCount(self, arr, n, k):
		map_ = {0: 1}
		out = 0
		sum_ = 0
		for num in arr:
			sum_ += num
			mod = sum_ % k
			if mod in map_:
				out += map_[mod]
			else:
				map_[mod] = 0
			map_[mod] += 1
		return out


class Solution:

	def subCount(self, arr, n, k):
		m = [0 for i in range(k + 1)]
		s = 0
		for i in arr:
			s += i
			a = (s % k + k) % k
			m[a] += 1
		ans = 0
		for i in m:
			if i > 1:
				ans += i * (i - 1) // 2
		ans += m[0]
		return ans


class Solution:

	def subCount(self, arr, n, k):
		count = 0
		prefix = [0]
		for i in range(len(arr)):
			prefix.append(prefix[-1] + arr[i])
		freq = {}
		for i in prefix:
			if i % k in freq:
				count += freq[i % k]
				freq[i % k] += 1
			elif i % k not in freq:
				freq[i % k] = 0
				freq[i % k] += 1
		return count


from collections import Counter

class Solution:

	def subCount(self, arr, n, k):
		hashmap = Counter({0: 1})
		cur_sum = ans = 0
		for index in range(n):
			cur_sum += arr[index]
			ans += hashmap[cur_sum % k]
			hashmap[cur_sum % k] += 1
		return ans


class Solution:

	def subCount(self, arr, n, k):
		nums = arr
		pref_sum = 0
		mp = {}
		c = 0
		for (i, val) in enumerate(nums):
			pref_sum += val
			if pref_sum % k == 0:
				c += 1
			if pref_sum % k in mp:
				c += mp[pref_sum % k]
			if pref_sum % k in mp:
				mp[pref_sum % k] += 1
			else:
				mp[pref_sum % k] = 1
		return c


class Solution:

	def subCount(self, arr, n, k):
		res = {0: 1}
		summ = 0
		count = 0
		for i in range(n):
			summ += arr[i]
			rem = summ % k
			if rem in res:
				count += res[rem]
				res[rem] += 1
			else:
				res[rem] = 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		h = {0: 1}
		c = 0
		summ = 0
		for i in arr:
			summ += i
			r = summ % k
			if r in h:
				c += h[r]
				h[r] += 1
			else:
				h[r] = 1
		return c


class Solution:

	def subCount(self, arr, n, k):
		ans = 0
		sum = 0
		m = {0: 1}
		for i in arr:
			sum += i
			mod = sum % k
			if mod < 0:
				mod = k - mod
			if mod in m:
				ans += m[mod]
				m[mod] += 1
			else:
				m[mod] = 1
		return ans


class Solution:

	def subCount(self, arr, n, k):
		d = {0: 1}
		summ = 0
		rem = 0
		c = 0
		for i in range(n):
			summ += arr[i]
			rem = summ % k
			if rem < 0:
				summ += k
			if rem in d:
				c += d[rem]
				d[rem] += 1
			else:
				d[rem] = 1
		return c


from collections import Counter

class Solution:

	def subCount(self, arr, n, k):
		nums = [0]
		for n in arr:
			nums.append((nums[-1] + n) % k)
		X = sum(map(lambda x: x * (x - 1), Counter(nums).values())) // 2
		return X


class Solution:

	def subCount(self, arr, n, k):
		c = 0
		sum = 0
		d = {0: 1}
		for i in range(n):
			sum += arr[i]
			if sum % k not in d:
				d[sum % k] = 1
			else:
				c += d[sum % k]
				d[sum % k] += 1
		return c


from collections import defaultdict

class Solution:

	def subCount(self, arr, n, K):
		m = defaultdict(int)
		m[0] += 1
		ans = 0
		sum = 0
		for i in range(n):
			sum += arr[i]
			r = sum % K
			if r < 0:
				r = r + K
			if r in m:
				ans += m[r]
			m[r] += 1
		return ans


class Solution:

	def subCount(self, nums, n, k):
		count = 0
		s = 0
		dic = {0: 1}
		for i in range(len(nums)):
			s += nums[i]
			if s % k < 0:
				if s % k + k not in dic:
					dic[s % k + k] = 1
				else:
					count += dic[s % k + k]
					dic[s % k + k] += 1
			elif s % k not in dic:
				dic[s % k] = 1
			else:
				count += dic[s % k]
				dic[s % k] += 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		h = {0: 1}
		sum1 = 0
		c = 0
		for i in range(len(arr)):
			sum1 += arr[i]
			r = sum1 % k
			if r in h:
				c += h[r]
				h[r] += 1
			else:
				h[r] = 1
		return c


class Solution:

	def subCount(self, arr, n, k):
		d = {}
		prefix_sum = 0
		count = 0
		d[0] = 1
		for i in range(n):
			prefix_sum += arr[i]
			if prefix_sum % k in d:
				count += d[prefix_sum % k]
				d[prefix_sum % k] += 1
			else:
				d[prefix_sum % k] = 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		from collections import defaultdict
		d = defaultdict(int)
		d[0] = 1
		pre = 0
		res = 0
		for i in range(n):
			pre += arr[i]
			mod = pre % k
			if mod < 0:
				mod += k
			if d[mod] > 0:
				res += d[mod]
			d[mod] += 1
		return res


class Solution:

	def subCount(self, arr, n, k):
		import collections
		summ = 0
		count = 0
		mapp = collections.defaultdict(int)
		mapp[0] = 1
		for ele in arr:
			summ += ele
			count += mapp[summ % k]
			mapp[summ % k] += 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		d = {0: 1}
		c = 0
		t = 0
		for i in range(n):
			t += arr[i]
			h = (t % k + k) % k
			if h in d:
				c += d[h]
				d[h] += 1
			else:
				d[h] = 1
		return c


class Solution:

	def subCount(self, arr, n, k):
		dic = {0: 1}
		ct = pref = 0
		for i in range(n):
			pref += arr[i]
			val = pref % k
			if val in dic:
				ct += dic[val]
			dic[val] = 1 + dic.get(val, 0)
		return ct


class Solution:

	def subCount(self, arr, n, k):
		sum = 0
		count = 0
		dict = {0: 1}
		for element in arr:
			sum += element
			remainder = sum % k
			if remainder not in dict:
				dict[remainder] = 1
			else:
				count += dict[remainder]
				dict[remainder] += 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		sum = 0
		sum_list = {0: 1}
		result = 0
		for i in arr:
			sum += i
			key = sum % k
			if key in sum_list:
				result += sum_list[key]
				sum_list[key] += 1
				continue
			sum_list[key] = 1
		return result


class Solution:

	def subCount(self, arr, n, k):
		m = []
		for i in range(k + 1):
			m.append(0)
		cu_sum = 0
		for i in range(n):
			cu_sum = cu_sum + arr[i]
			m[(cu_sum % k + k) % k] += 1
		result = 0
		for i in range(k):
			if m[i] > 1:
				result += m[i] * (m[i] - 1) // 2
		result += m[0]
		return result


class Solution:

	def subCount(self, arr, n, k):
		(total, count, d) = (0, 0, {0: 1})
		for (i, v) in enumerate(arr):
			total += v
			remainder = total % k
			if remainder not in d:
				d[remainder] = 1
			else:
				count += d[remainder]
				d[remainder] += 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		total = 0
		count = 0
		d = {0: 1}
		for (i, ele) in enumerate(arr):
			total += ele
			reminder = total % k
			if reminder in d:
				count += d[reminder]
				d[reminder] += 1
			else:
				d[reminder] = 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		sum = 0
		res = 0
		di = {}
		rem = 0
		di[0] = 1
		for i in range(len(arr)):
			sum = sum + arr[i]
			rem = sum % k
			if rem in di:
				res += di[rem]
				di[rem] += 1
			else:
				di[rem] = 1
		return res


class Solution:

	def subCount(self, arr, n, k):
		l = []
		sm = 0
		c = 0
		d = {}
		for i in range(n):
			sm += arr[i]
			l.append(sm)
		for i in range(n):
			l[i] = l[i] % k
		for i in range(n):
			if l[i] in d:
				d[l[i]] += 1
			else:
				d[l[i]] = 1
		for (key, v) in d.items():
			if key == 0:
				c += v
			c += v * (v - 1) // 2
		return c


class Solution:

	def subCount(self, nums, n, k):
		freq = {0: 1}
		sum1 = 0
		rem = 0
		count = 0
		for i in range(len(nums)):
			sum1 += nums[i]
			rem = sum1 % k
			if rem < 0:
				rem = rem + k
				if rem in freq:
					count += freq[rem]
					freq[rem] += 1
				else:
					freq[rem] = 1
			elif rem in freq:
				count += freq[rem]
				freq[rem] += 1
			else:
				freq[rem] = 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		sm = 0
		pre = [0] * 100000
		pre[0] = 1
		for i in arr:
			sm += i
			sm = (k + sm) % k
			pre[sm] += 1
		ans = 0
		for i in pre:
			ans += i * (i - 1) // 2
		return ans


class Solution:

	def subCount(self, arr, n, k):
		counts = [0] * k
		summ = 0
		for i in range(n):
			summ += arr[i] % k
			counts[summ % k] += 1
		res = counts[0]
		for c in counts:
			res += c * (c - 1) // 2
		return res


class Solution:

	def subCount(self, arr, n, k):
		d = {0: 1}
		cum_sum = 0
		ans = 0
		for i in range(n):
			cum_sum += arr[i]
			if cum_sum % k in d:
				ans += d[cum_sum % k]
				d[cum_sum % k] += 1
			else:
				d[cum_sum % k] = 1
		return ans


class Solution:

	def subCount(self, arr, n, k):
		mod = []
		for i in range(k + 1):
			mod.append(0)
		cum_sum = 0
		for i in range(n):
			cum_sum += arr[i]
			mod[(cum_sum % k + k) % k] += 1
		sub_count = 0
		for i in range(k):
			if mod[i] > 1:
				sub_count += mod[i] * (mod[i] - 1) // 2
		sub_count += mod[0]
		return sub_count


class Solution:

	def subCount(self, arr, n, k):
		m = {}
		c = 0
		s = 0
		for i in arr:
			s += i
			if s % k == 0:
				c += 1
			if s % k in m:
				c += m[s % k]
			if s % k in m:
				m[s % k] += 1
			else:
				m[s % k] = 1
		return c


class Solution:

	def subCount(self, arr, n, k):
		size = k + 1
		rem = [0] * size
		pair = 0
		pref_sum = [0] * n
		pref_sum[0] = arr[0]
		for i in range(1, n):
			pref_sum[i] = pref_sum[i - 1] + arr[i]
		for i in range(n):
			temp = pref_sum[i] % k
			rem[temp] += 1
		for i in range(size):
			if rem[i] > 1:
				res = rem[i] * (rem[i] - 1)
				pair += res // 2
		pair += rem[0]
		return pair


class Solution:

	def subCount(self, arr, n, k):
		sums = 0
		counts = [0] * k
		for i in arr:
			sums += i
			counts[sums % k] += 1
		res = counts[0]
		for i in counts:
			res += i * (i - 1) // 2
		return res


class Solution:

	def subCount(self, arr, n, k):
		freq = [0] * k
		cnt = 0
		for i in range(1, len(arr)):
			arr[i] += arr[i - 1]
		for i in range(len(arr)):
			arr[i] = arr[i] % k
		freq[0] = 1
		for i in range(len(arr)):
			freq[arr[i]] += 1
		for i in range(k):
			if freq[i] > 0:
				cnt += freq[i] * (freq[i] - 1) // 2
		return cnt


class Solution:

	def subCount(self, arr, n, k):
		rem = {0: 1}
		curr_sum = 0
		ans = 0
		for i in arr:
			curr_sum += i
			remainder = curr_sum % k
			if remainder < 0:
				remainder += k
			if remainder not in rem:
				rem[remainder] = 1
			else:
				ans += rem[remainder]
				rem[remainder] += 1
		return ans


class Solution:

	def subCount(self, arr, n, k):
		mod = [0] * k
		sum = 0
		res = 0
		for x in arr:
			sum += x
			mod[sum % k] += 1
		for i in range(k):
			if mod[i] > 1:
				res += mod[i] * (mod[i] - 1) // 2
		return res + mod[0]


class Solution:

	def subCount(self, arr, n, k):
		mod = []
		for i in range(k + 1):
			mod.append(0)
		summ = 0
		for i in range(n):
			summ += arr[i]
			mod[(summ % k + k) % k] += 1
		count = 0
		for i in range(k):
			if mod[i] > 1:
				count += mod[i] * (mod[i] - 1) // 2
		count += mod[0]
		return count


class Solution:

	def subCount(self, arr, n, k):
		(mp, total, count) = ({0: 1}, 0, 0)
		for i in arr:
			total += i
			rem = total % k
			if rem in mp:
				count += mp[rem]
				mp[rem] += 1
			else:
				mp[rem] = 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		res = {0: 1}
		cumsum = 0
		count = 0
		for i in range(n):
			cumsum += arr[i]
			rem = cumsum % k
			if rem in res:
				count += res[rem]
				res[rem] += 1
			else:
				res[rem] = 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		l = list(map(int, input().split()))
		n = l[0]
		k = l[1]
		a = list(map(int, input().split()))
		ob = Solution()
		print(ob.subCount(a, n, k))


class Solution:

	def subCount(self, arr, n, k):
		a = {0: 1}
		sum1 = 0
		ans = 0
		for i in range(len(arr)):
			sum1 = sum1 + arr[i]
			rem = sum1 % k
			if rem not in a:
				a[rem] = 1
			else:
				ans = ans + a[rem]
				a[rem] = a[rem] + 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		l = list(map(int, input().split()))
		n = l[0]
		k = l[1]
		a = list(map(int, input().split()))
		ob = Solution()
		print(ob.subCount(a, n, k))


class Solution:

	def subCount(self, arr, n, k):
		has = {}
		su = 0
		for i in arr:
			su += i
			r = su % k
			if r in has:
				has[r] += 1
			else:
				has[r] = 1
		ans = 0
		for (k, v) in has.items():
			if k == 0:
				ans += v
			ans += v * (v - 1) // 2
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		l = list(map(int, input().split()))
		n = l[0]
		k = l[1]
		a = list(map(int, input().split()))
		ob = Solution()
		print(ob.subCount(a, n, k))


class Solution:

	def subCount(self, arr, n, k):
		(prefix, hash_table) = ([0], {0: 1})
		for num in arr:
			prefix.append((prefix[-1] + num) % k)
			if prefix[-1] not in hash_table:
				hash_table[prefix[-1]] = 0
			hash_table[prefix[-1]] += 1
		result = 0
		for key in list(hash_table.keys()):
			n = hash_table[key]
			result += n * (n - 1) // 2
		return result
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		l = list(map(int, input().split()))
		n = l[0]
		k = l[1]
		a = list(map(int, input().split()))
		ob = Solution()
		print(ob.subCount(a, n, k))


class Solution:

	def subCount(self, arr, n, k):
		s = {0: 1}
		curr_sum = 0
		count = 0
		for i in range(len(arr)):
			curr_sum += arr[i]
			rem = curr_sum % k
			if rem < 0:
				rem += k
			if rem in s:
				count += s[rem]
				s[rem] += 1
			if rem not in s:
				s[rem] = 1
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		l = list(map(int, input().split()))
		n = l[0]
		k = l[1]
		a = list(map(int, input().split()))
		ob = Solution()
		print(ob.subCount(a, n, k))


from collections import defaultdict

class Solution:

	def subCount(self, nums, n, k):
		n = len(nums)
		ans = 0
		hash_ = defaultdict(int)
		hash_[0] = 1
		sum_ = 0
		for i in range(n):
			sum_ += nums[i]
			ans += hash_.get(sum_ % k, 0)
			hash_[sum_ % k] += 1
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		l = list(map(int, input().split()))
		n = l[0]
		k = l[1]
		a = list(map(int, input().split()))
		ob = Solution()
		print(ob.subCount(a, n, k))


class Solution:

	def subCount(self, arr, n, k):
		dict = {}
		currsum = 0
		c = 0
		dict[0] = 1
		for i in range(len(arr)):
			currsum += arr[i]
			rem = currsum % k
			if rem < 0:
				rem += k
			if rem in dict.keys():
				c += dict.get(rem)
			dict[rem] = 1 + dict.get(rem, 0)
		return c


class Solution:

	def subCount(self, arr, n, k):
		s = {0: 1}
		(curr_sum, count) = (0, 0)
		for i in range(n):
			curr_sum += arr[i]
			rem = curr_sum % k
			if rem < 0:
				rem += k
			if rem not in s:
				s[rem] = 1
			else:
				count += s[rem]
				s[rem] += 1
		return count


class Solution:

	def subCount(self, a, n, k):
		ans = 0
		cumSum = 0
		d = {}
		d[cumSum] = 1
		for i in range(n):
			cumSum += a[i]
			remainder = cumSum % k
			if remainder in d:
				ans += d[remainder]
				d[remainder] += 1
			else:
				d[remainder] = 1
		return ans


class Solution:

	def subCount(self, arr, n, k):
		mp = {}
		mp[0] = 1
		count = 0
		currsum = 0
		for i in range(n):
			currsum += arr[i]
			mod = (currsum % k + k) % k
			if mod in mp.keys():
				count += mp[mod]
				mp[mod] += 1
			else:
				mp[mod] = 1
		return count


class Solution:

	def subCount(self, a, n, k):
		map = {}
		count = 0
		prefix = 0
		for i in range(len(a)):
			prefix += a[i]
			if (prefix - k) % k in map:
				count += map[(prefix - k) % k]
			if prefix % k == 0:
				count += 1
			if prefix % k not in map:
				map[prefix % k] = 1
			else:
				map[prefix % k] += 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		maps = {0: 1}
		res = 0
		pref = 0
		for i in range(n):
			pref += arr[i]
			mod = pref % k
			if mod in maps:
				res += maps[mod]
			maps[mod] = 1 + maps.get(mod, 0)
		return res


class Solution:

	def subCount(self, arr, n, k):
		from collections import defaultdict
		(running_sum, dict1, count) = (0, defaultdict(int), 0)
		dict1[0] = 1
		for i in arr:
			running_sum += i
			if running_sum % k in dict1:
				count += dict1[running_sum % k]
			dict1[running_sum % k] += 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		d = {0: 1}
		sum = 0
		ans = 0
		for i in range(len(arr)):
			sum += arr[i]
			rem = sum % k
			if rem < 0:
				rem + k
			if rem in d:
				ans += d[rem]
				d[rem] += 1
			else:
				d[rem] = 1
		return ans


class Solution:

	def subCount(self, arr, n, k):
		freq = {}
		prefixSum = 0
		freq[0] = 1
		count = 0
		for x in arr:
			prefixSum += x
			remainder = prefixSum % k
			if remainder in freq:
				count += freq[remainder]
				freq[remainder] += 1
			else:
				freq[remainder] = 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		ans = 0
		um = {0: 1}
		sum = 0
		rem = 0
		for i in range(n):
			sum += arr[i]
			rem = sum % k
			if rem < 0:
				rem += k
			if rem in um.keys():
				ans += um[rem]
				um[rem] += 1
			else:
				um[rem] = 1
		return ans


class Solution:

	def subCount(self, b, n, k):
		c = [0] * k
		sum = 0
		for i in range(len(b)):
			sum += b[i]
			c[sum % k] += 1
		result = c[0]
		for i in c:
			result += i * (i - 1) // 2
		return result


class Solution:

	def subCount(self, arr, n, k):
		count = 0
		map = {}
		cur = 0
		for i in range(len(arr)):
			cur += arr[i]
			rem = cur % k
			if rem == 0:
				count += 1
			if rem in map:
				count += map[rem]
			if rem not in map:
				map[rem] = 1
			else:
				map[rem] += 1
		return count


from collections import defaultdict

class Solution:

	def subCount(self, arr, n, k):
		hm = defaultdict(lambda : 0)
		hm[0] = 1
		currSum = 0
		count = 0
		for i in range(0, n, 1):
			currSum += arr[i]
			if currSum % k in hm:
				count += hm[currSum % k]
			hm[currSum % k] += 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		Dict_ = {0: 1}
		Sum = 0
		cnt = 0
		for i in range(n):
			Sum += arr[i]
			rem = Sum % k
			if rem < 0:
				rem = rem + k
			if rem not in Dict_:
				Dict_[rem] = 1
			else:
				cnt += Dict_[rem]
				Dict_[rem] += 1
		return cnt


from collections import defaultdict

class Solution:

	def subCount(self, arr, n, k):
		d = defaultdict(lambda : 0)
		d[0] += 1
		cs = 0
		count = 0
		for i in arr:
			cs += i
			if cs % k in d:
				count += d[cs % k]
			d[cs % k] += 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		pmap = {0: 1}
		count = 0
		psum = 0
		for val in arr:
			psum += val
			rem = psum % k
			if rem < 0:
				rem += k
			if rem in pmap:
				count += pmap[rem]
				pmap[rem] += 1
			else:
				pmap[rem] = 1
		return count


class Solution:

	def subCount(self, arr, n, k):
		dic = {}
		for j in range(k + 1):
			dic[j] = 0
		dic[0] = 1
		pre = [arr[0]]
		for j in range(1, n):
			pre.append(pre[-1] + arr[j])
		c = 0
		for j in pre:
			rem = j % k
			dic[rem] += 1
			c += dic[rem] - 1
		return c


class Solution:

	def subCount(self, arr, n, k):
		dic = {0: 1}
		curr_sum = 0
		subArrays = 0
		for i in range(n):
			curr_sum += arr[i]
			rem = curr_sum % k
			if rem < 0:
				rem += k
			if rem in dic:
				subArrays += dic[rem]
				dic[rem] += 1
			else:
				dic[rem] = 1
		return subArrays