(chiaphan.*)

Cho dãy số nguyên \(A = (a_{1},\ a_{2},\ ...,\ a_{n})\); Hãy đếm số cách chia dãy trên thành 4 dãy con gồm các số liên tiếp của \(A\) sao cho tổng các số trong mỗi dãy con đều bằng nhau. Chính xác hơn, mỗi cách chia được mô tả bằng bộ 3 chỉ số\((i,j,k)\): \(1 \leq i < j < k < n\) . Trong đó (\(a_{1},a_{2},\ldots,\ a_{i}\)) là dãy 1; \({(a}_{i + 1},a_{i + 2},\ldots,\ a_{j})\)là dãy 2; \({(a}_{j + 1},a_{j + 2},\ldots,\ a_{k})\) là dãy 3 và \({(a}_{k + 1},a_{k + 2},\ldots,\ a_{n})\) là dãy 4. Hai cách chia khác nhau ứng với hai bộ 3 chỉ số \((i,j,k)\) khác nhau.

Dữ liệu vào:

+ Dòng đầu tiên ghi số nguyên dương \(n\ (n \leq 10^{6})\)

+ Dòng thứ hai ghi \(n\) số nguyên \(a_{1},a_{2},\ldots,\ a_{n}\ (\left| a_{i} \right| \leq 10^{9};i = 1,2,\ldots,n)\); hai số liên tiếp cách nhau bằng một dấu trống

Kết quả:

+ Ghi một số nguyên là số lượng cách chia tìm được

Ví dụ:

Ràng buộc:

+ Có 2/6 tests có \(n \leq 50\)

+ Có 2/6 tests khác có \(n \leq 500\)

+ Có 1/6 tests khác có \(n \leq 5000\)

+ Có 1/6 tests còn lại có \(n \leq 10^{6}\)