Một dãy các số nguyên được gọi là dãy bội ba nếu với mỗi giá trị xuất hiện trong dãy thì giá trị đó xuất hiện đúng ba lần. Ví dụ:

• ~(1, 1, 1)~ là dãy bội ba.
• ~(1, 2, 2, 1, 1, 2)~ là dãy bội ba.
• ~(1, 3, 3, 3, 3, 1)~ không phải là dãy bội ba.

Cho dãy ~a~ gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~. Gọi ~f(i, j)~, với ~1 \le i \le j \le n~, là số cách chia dãy ~a_i, a_{i+1}, \dots, a_j~ thành các dãy con liên tiếp (mỗi phần tử ~a_k~ với ~i \le k \le j~ thuộc đúng một dãy con) sao cho mỗi dãy con đều là một dãy bội ba.

Yêu cầu: Hãy tính tổng các ~f(i, j)~ của tất cả các dãy con liên tiếp của ~a~, tức là tính ~\sum_{i=1}^{n} \sum_{j=i}^{n} f(i, j)~. Vì kết quả có thể rất lớn nên chỉ cần đưa ra số dư trong phép chia kết quả cho ~(10^9 + 7)~.

Input

• Dòng đầu tiên gồm một số nguyên dương ~n~ ~(1 \le n \le 3 \times 10^5)~.
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(1 \le a_i \le n)~.

Output

• Ghi ra một số nguyên duy nhất là kết quả bài toán.

Sample Input 1

6
1 1 1 2 2 2

Sample Output 1

4

Sample Input 2

9
1 2 3 3 3 1 2 1 2

Sample Output 2

2