Chia ba

Cho một dãy $a$ gồm $n$ số nguyên không âm $a_1,a_2,\dots ,a_n$. Hãy chia dãy $a$ thành ba đoạn con, đoạn thứ nhất gồm một hoặc một số các phần tử đầu tiên của dãy $a$, đoạn thứ hai gồm một hoặc một số phần tử tiếp theo của dãy $a$, đoạn thứ ba gồm các phần tử còn lại của dãy $a$ thỏa mãn các điều kiện sau:

• Tổng các phần tử của đoạn con thứ nhất chia hết cho $3$.
• Tổng các phần tử của đoạn con thứ hai chia $3$ dư $1$.
• Tổng các phần tử của đoạn con thứ ba chia $3$ dư $2$.

Hai cách chia được coi là khác nhau nếu vị trí kết thúc của đoạn thứ nhất hoặc của đoạn thứ hai khác nhau.

Yêu cầu: Hãy cho biết có bao nhiêu cách chia dãy $a$ thỏa mãn các điều kiện trên.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương $n$ là số phần tử của dãy $a$ $(1\le n\le {10}^6)$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$ $(0\le a_i\le {10}^9$ với $1\le i\le n)$.

Dữ liệu ra

In ra một số nguyên duy nhất là số cách chia dãy $a$ thỏa mãn các điều kiện trên.

Ràng buộc

• $1\le n\le {10}^6$.
• $0\le a_i\le {10}^9$ với $1\le i\le n$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($30\%$ số test): $3\le n\le 100$.
• Subtask 2 ($40\%$ số test): $100<n\le 5000$.
• Subtask 3 ($30\%$ số test): $5000<n\le {10}^6$.

Ví dụ