Count Divisible Subarrays

You are given an array arr of integers and an integer k. Your task is to determine the number of contiguous subarrays (i.e. segments of the array) whose sum is divisible by k.

The subarray is defined as a contiguous segment of the array. Formally, for an array of length n, a subarray can be denoted by arr[i...j] (0 ≤ i ≤ j < n). You need to compute the sum of every possible subarray and count how many of these sums are divisible by k (i.e. the sum modulo k equals 0).

The problem can be understood mathematically as finding the number of pairs of indices (i, j) such that:

Efficient solutions typically involve the use of prefix sums and counting the remainders.

inputFormat

The first line of input contains two integers n and k, separated by a space, where n is the number of elements in the array.

The second line contains n space-separated integers representing the array arr.

outputFormat

Output a single integer which is the count of subarrays whose sums are divisible by k.

5 3
1 2 3 4 1

4