765. Sridharan and the Shopkeeper
0
Medium
Sridharan, a chocolate enthusiast, visited a shop that had an array of integers representing the number of chocolates at each index. Sridharan wants to obtain multiple of K chocolates. The shopkeeper has agreed to provide all subarrays whose sum of chocolates is divisible by K. Your task is to determine the total number of ways Sridharan can obtain chocolates. In other words, you need to find the number of non-empty subarrays whose sum is divisible by K.
Input Format
The first line of the input contains two integers N and K, representing the size of the array and the value of K, respectively. The second line contains N integers, each representing the number of chocolates at the corresponding index in the array.
Output Format
Print the total number of ways Sridharan can obtain chocolates. Note: If arr[i] is negative, it means Sridharan has to give arr[i] chocolates to the shopkeeper.
Example
Input
6 5
4 5 0 -2 -3 1
Output
7
Constraints
1<=N<=10^5
-10^5<=arr[i]<=10^5
2<=k<=10^4
-10^5<=arr[i]<=10^5
2<=k<=10^4
Loading...
View Submissions
Console