Chia đoạn

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 \(3\) 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, \ldots, a_n\). Gọi \(f(i, j)\) (\(1 \le i \le j \le n\)) là số cách chia \(a_i, a_{i+1}, \ldots, a_j\) thành các dãy con liên tiếp (mỗi phần tử \(a_k\) (\(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 \(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:

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 chứa một số nguyên \(n\) (\(1 \le n \le 3 \times 10^5\));

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le n\), \(1 \le i \le n\)).

Ràng buộc:

• Có \(20\%\) số điểm thỏa mãn điều kiện \(n \le 80\);

• Có \(20\%\) số điểm thỏa mãn điều kiện \(n \le 200\);

• Có \(15\%\) số điểm thỏa mãn điều kiện \(n \le 7000\);

• Có \(30\%\) số điểm thỏa mãn điều kiện \(n \le 3 \times 10^5\), \(a_i \le 16\), \(1 \le i \le n\);

• Có \(15\%\) số điểm không có ràng buộc gì thêm.

Output

In ra một số nguyên duy nhất là kết quả của bài toán (sau khi lấy phần dư khi chia cho \(10^9 + 7\)).

Example 1

Input:

6
1 1 1 2 2 2

Output:

4

Example 2

Input:

9
1 2 3 3 3 1 2 1 2

Output:

2

Note

Ở ví dụ thứ nhất: \(f(1, 3) = 1\), \(f(4, 6) = 1\) và \(f(1, 6) = 2\) (chia thành hai dãy \((1,1,1)\) và \((2,2,2)\), hoặc để nguyên cả dãy vì \((1,1,1,2,2,2)\) cũng là dãy bội ba). Các đoạn còn lại có \(f = 0\). Tổng bằng \(1 + 1 + 2 = 4\).

Ở ví dụ thứ hai: \(f(3, 5) = 1\) (đoạn \(3, 3, 3\)) và \(f(1, 9) = 1\) (cả dãy là một dãy bội ba duy nhất). Tổng bằng \(2\).