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

Explanation

1. 5 2 3 4 6

2. 5 2 3 4 6

3. 5 2 3 4 6

4. 5 2 3 4 6

5. 5 2 3 4 6

6. 5 2 3 4 6