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~.

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.

Input

• 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~.

Output

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.

Scoring

Sample Input 1

7
2 1 3 0 4 0 5

Sample Output 1

6