Cho một mảng gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~. Một đoạn con là một dãy phần tử liên tiếp, được xác định bởi hai đầu mút ~l~ và ~r~ với ~1 ≤ l ≤ r ≤ n~.

Hãy đếm số đoạn con có tổng chia hết cho ~n~.

Input

• Dòng đầu chứa số nguyên ~n~, là số phần tử của mảng và cũng là số chia cần xét.
• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, ..., a_n~.

Output

• In một số nguyên là số đoạn con có tổng chia hết cho ~n~.

Giới hạn

• ~1 ≤ n ≤ 2 × 10^5~.
• ~-10^9 ≤ a_i ≤ 10^9~ với mọi ~1 ≤ i ≤ n~.

Ví dụ

Input

5
3 1 2 7 4

Output

1

Giải thích ví dụ

Đoạn từ vị trí 2 đến vị trí 4 có tổng 1 + 2 + 7 = 10, chia hết cho 5. Không có đoạn con nào khác thỏa mãn, nên kết quả là 1.