Cắt dải giấy 2

Cho một dải giấy gồm $n$ ô xếp thành hàng ngang, ô thứ $i$ ghi một số nguyên $a_i$ (có thể âm).

Hãy đếm số cách cắt dải giấy thành ba phần liên tiếp sao cho:

• Mỗi phần chứa ít nhất một ô (số ô là số nguyên dương).
• Tổng các số trong ba phần bằng nhau.

Việc cắt chỉ được thực hiện dọc theo các đường biên giữa hai ô liền kề. Hai cách cắt được coi là khác nhau nếu vị trí ít nhất một đường cắt khác nhau.

Dữ liệu vào

• Dòng đầu chứa số nguyên $n$ là số ô của dải giấy.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

• Một số nguyên duy nhất là số cách cắt hợp lệ.

Ràng buộc

• $1\le n\le {10}^5$
• $|a_i|\le {10}^4$
• Đáp án có thể vượt quá phạm vi số nguyên 32 bit.

Ví dụ