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

Cho dãy gồm n số nguyên a1, a2,…, an (1 ≤ ai ≤ 3, I = 1 g 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 cọi là một cách) mà vẫn giữ 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.

VD: 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.

Dữ lIệu:

+ Dòng 1: số nguyên dương n (n ≤ 106) là số lượng phần tử của dãy.

+ Dòng 2: ghi n số nguyên a1, a2,…, an là giá trị của các phần tử của dãy ban đầu

Kết quả: 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 (109 + 7)

Ví dụ: 

INP
 

8

1 2 1 2 3 1 2 3

OUT

15