Vừa mới học xong kiến thức tính chất chia hết, Tuấn và Minh muốn cùng nhau kiểm tra các kiến thức vừa học. Tuấn viết một dãy số gồm ~n~ số nguyên không âm ~a_1, a_2, \dots, a_n~ sau đó đố Minh có bao nhiêu số trong dãy chia hết cho ~n~. Vấn đề thật đơn giản, lần lượt thử kiểm tra từng số một với ~n~. Sau khi đếm xong số lượng số chia hết cho ~n~, Minh nhận thấy bài toán hơi nhàm chán liền nảy ra một ý, một bài toán vẫn có thể kiểm tra về kiến thức tính chia hết mà không tầm thường, đó là: đếm số lượng dãy con liên tiếp có tổng chia hết cho ~n~ rồi đố Tuấn.

Yêu cầu: Cho ~n~ và dãy số nguyên không âm ~a_1, a_2, \dots, a_n~, hãy đếm số lượng dãy con liên tiếp có tổng chia hết cho ~n~.

Input

• Dòng 1: chứa số nguyên ~n~ (~n \le 10^5~)
• ~n~ dòng sau (từ dòng 2 đến dòng ~n + 1~), mỗi dòng chứa một số nguyên không âm ~a_i~ (~a_i \le 10^{50}~)

Output

• Ghi ra một số duy nhất là số lượng dãy con đếm được.

Sample Input 1

3
3
2
1

Sample Output 1

3