372. 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. Determine the total number of ways Sridharan can obtain chocolates, i.e., the number of non-empty subarrays with a sum divisible by K.

Input Format

The first line of input contains two integers N (size of the array) and K. The second line contains N integers representing the number of chocolates at each 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