Mảng con chia hết

Trong một buổi giao lưu văn hóa, FullHouse Dev được giới thiệu về một trò chơi dân gian độc đáo liên quan đến việc chia nhóm. Trò chơi này đã truyền cảm hứng cho họ tạo ra một bài toán thú vị về mảng và tính chia hết. Với tinh thần tò mò và ham học hỏi, FullHouse Dev đã bắt tay vào giải quyết bài toán này.

Bài toán

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là đếm số lượng mảng con mà tổng các giá trị trong mảng con đó chia hết cho \(n\).

INPUT FORMAT:

• Dòng đầu tiên chứa một số nguyên \(n\): kích thước của mảng.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\): các phần tử của mảng.

OUTPUT FORMAT:

• In ra một số nguyên: số lượng mảng con thỏa mãn yêu cầu.

Ràng buộc:

• \(1 \le n \le 2 \cdot 10^5\)
• \(-10^9 \le a_i \le 10^9\)

Ví dụ

INPUT

5
3 1 2 7 4

OUTPUT

1

Giải thích

Trong ví dụ này, chỉ có một mảng con thỏa mãn yêu cầu, đó là mảng con gồm toàn bộ các phần tử của mảng ban đầu. Tổng của mảng này là 3 + 1 + 2 + 7 + 4 = 17, và 17 chia hết cho 5 (kích thước của mảng).

FullHouse Dev nhận ra rằng bài toán này không chỉ là một thử thách về lập trình mà còn phản ánh cách mà văn hóa dân gian có thể truyền cảm hứng cho những bài toán toán học hiện đại. Họ quyết định sẽ tìm hiểu thêm về các trò chơi dân gian khác để tạo ra những bài toán thú vị và ý nghĩa trong tương lai.