#159Medium

Subarray divisibility

Time: 1 s · Memory: 256 MB

Prefix sums

Statement

You are given an array of $n$ integers. Count the non-empty subarrays whose sum is divisible by $n$ .

Input format

The first line contains $n$ ( $1 \le n \le 2 \cdot 10^5$ ). The second line contains $n$ integers ( $|a_i| \le 10^9$ ).

Output format

A single number — the number of subarrays.

Examples

Input

5
3 1 2 7 4

Output

Note

The sum of $[l, r]$ is divisible by $n$ $\iff$ $p_r \equiv p_{l-1} \pmod n$ . So count the remainders of $p_0, p_1, \ldots, p_n$ : a remainder that occurs $c$ times gives $\frac{c(c-1)}{2}$ pairs. An array of $n$ counters is enough.

There are negative numbers: in C++, Go and Java % returns a negative remainder — use $((p \bmod n) + n) \bmod n$ . The answer reaches $2 \cdot 10^{10}$ — a 64-bit type is needed.

Source: CSES, problem 1662.

Subarray divisibility

Time: 1 s · Memory: 256 MB

Prefix sums

Statement

You are given an array of $n$ integers. Count the non-empty subarrays whose sum is divisible by $n$ .

Input format

The first line contains $n$ ( $1 \le n \le 2 \cdot 10^5$ ). The second line contains $n$ integers ( $|a_i| \le 10^9$ ).

Output format

A single number — the number of subarrays.

Examples

Input

5
3 1 2 7 4

Output

Note

There are negative numbers: in C++, Go and Java % returns a negative remainder — use $((p \bmod n) + n) \bmod n$ . The answer reaches $2 \cdot 10^{10}$ — a 64-bit type is needed.

Source: CSES, problem 1662.