Cho dãy ~A=\{a_1, a_2, \ldots, a_n\}~ là các số nguyên dương có giá trị từ 1 đến 3. Có bao nhiêu cách để xóa đi một số phần tử của dãy (Không xóa phần tử nào cũng được xem là một cách) mà vẫn giữa nguyên thứ tự ban đầu để được một dãy mới thỏa mãn các yêu cầu sau:

1. Dãy còn ít nhất 3 phần tử.

2. Phần tử đầu tiên của dãy có giá trị 1, tiếp theo là một số phần tử có giá trị 2 (ít nhất có một số 2) và kết thúc bằng đúng một phần tử có giá trị 3.

Ví dụ dãy sau khi xóa có giá trị ~\{1, 2, 2, 3\}~ hoặc ~\{1, 2, 3\}~ là thỏa yêu cầu, ngược lại dãy ~\{1, 1, 2, 3\}~ hoặc ~\{1, 2, 3, 3\}~ là không thỏa yêu cầu.

Input

Dòng 1 chứa số nguyên ~n~ thỏa ~1 \le n \le 10^6~.

Dòng 2 chứa dãy số ~a_1, a_2, \ldots, a_n~.

Output

In ra kết quả cần đếm, do kết quả lớn nên cần modulo cho ~10^9+7~

Sample Input

8
1 2 1 2 3 1 2 3

Sample Output

15

REF HSG Vĩnh Phúc.