Subarray Sum Divisibility

You are given an array of integers and an integer \(k\). Your task is to determine the number of contiguous subarrays whose sums are divisible by \(k\). A subarray is a contiguous segment of the array.

Note: The division operation should be treated in such a way that the remainder is always non-negative. For example, if the subarray sum is negative, adjust the result appropriately.

Read input from stdin and print the answer to stdout.

inputFormat

The input consists of two lines:

• The first line contains two integers \(n\) and \(k\), where \(n\) is the number of elements in the array and \(k\) is the divisor.
• The second line contains \(n\) integers separated by spaces, representing the array elements.

outputFormat

Print a single integer representing the number of subarrays whose sum is divisible by \(k\).

5 3
1 2 3 4 1

4