Subarrays with sum divisible by n
Given an array of
n numbers, you would like to know how many subarrays are there that have a sum divisible by n.Input
The first line of the input contains two integers -
n the number of elements in the array (1 ≤ n ≤ ). The following line contains
n integers separated by a space, that represent the elements of the array .Output
The program should print a single integer - the number of subarrays whose sum is divisible by
n.Examples
Input | Output |
5
5 2 3 4 6 | 6 |
Explanation
52 3 4 6
52 34 6
5 2 34 6
5 2 34 6
52 3 4 6
5 2 3 4 6
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB