Tham gia Đại hội thể htao có \(n\) vận động viên có chiều cao đôi một phân biệt. Đánh số các vận động viên từ \(1\) đến \(n\) vận động viên có chiều cao đôi một phân biệt. Đánh số các vận động viên từ \(1\) đến \(n\), vận động viên thứ \(t\) (\(1 \le t \le n\)) có chiều cao \(h_i\). Theo yêu cầu \(n\) vận động viên sẽ được xếp thành một hàng dọc sao cho không tồn tại bộ ba vận động viên \(i,j,k\) thỏa mãn:

• Vận động viên \(i\) đứng trước vận động viên \(j\), vận động viên \(j\) đứng trước vận động viên \(k\).
• Chiều cao vận động viên \(j\) thấp hơn chiều cao vận động viên \(i\) và chiều cao vận động viên \(i\) thấp hơn chiều cao vận động viên \(k\).

Yêu cầu: Gọi \(s\) là số cách xếp thỏa mãn, tính \(s \% (10^9+7)\), trong đó \(\%\) là phép toán chia lấy dư.

Input

• Dòng đầu chứa số nguyên dương \(n\) (\(n \ge 3\)).
• Dòng thứ hai gồm \(n\) số nguyên dương \(h_1,h_2,...,h_n\) (\(h_i \le 10^9\)).

Output

• Gồm một dòng chứa một số nguyên là kết quả bài toán.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 10\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 20\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 10^3\).
• Subtask \(4\) (\(20\%\) số điểm): \(n \le 10^6\).

Example

3
1 2 3

5