Cho dãy gồm ~n~ số nguyên ~a_1,a_2,…,a_n~ ~(1≤a_i≤3,∀i=1→n)~. 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 coi 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 hai 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ị là 2 (ít nhất có 1 số 2) và kết thúc bằng đúng một phần tử có giá trị là 3. Ví dụ: các dãy {1, 2, 2, 3} và dãy {1, 2, 3} thỏa mãn yêu cầu; các dãy {1, 2, 3, 3) và dãy {1, 1, 2, 3} không thỏa mãn yêu cầu.

Input: Vào từ file văn bản DELETE.INP:

• Dòng 1: số nguyên dương ~n~ ~(n≤10^6)~ là số lượng phần tử của dãy.
• Dòng 2: ghi ~n~ số nguyên ~a_1,a_2,…,a_n~ là giá trị của các phần tử của dãy ban đầu.

Output: Ghi ra file văn bản DELETE.OUT:

• Gồm một dòng duy nhất là số cách xóa để được dãy mới thỏa mãn yêu cầu của đề bài. Do số lượng cách xóa phần tử có thể rất lớn nên bạn chỉ cần ghi ra số lượng cách xóa sau khi chia lấy dư cho ~(10^9+7)~

Sample Input 1

8
1 2 1 2 3 1 2 3

Sample Output 1

15