Subarray Divisibility Solution | CSES Problem | Number of subarray divisible by k

 

Subarray Divisibility

Given an array of n$n$ integers, your task is to count the number of subarrays where the sum of values is divisible by n$n$.

Input

The first input line has an integer n$n$: the size of the array.

The next line has n$n$ integers a1,a2,…,an$a_1,a_2,\dots ,a_n$: the contents of the array.

Output

Print one integer: the required number of subarrays.

Constraints

• 1≤n≤2⋅105$1\le n\le 2\cdot {10}^5$
  
• −109≤ai≤109$-{10}^9\le a_i\le {10}^9$
  

Example

Input:
5
3 1 2 7 4

Output:
1