Cho dãy gồm \(n\) số nguyên \(a_1, a_2, ..., a_n\) (\(1 \leq a_i \leq 3, \forall i = 1 \to 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

• Dòng 1: số nguyên dương \(n\) (\(n \leq 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

• 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)\)

Example

8
1 2 1 2 3 1 2 3

15