Fred the Farmer muốn thiết kế lại hàng rào của ngôi nhà mình. Hàng rào của Fred bao gồm $n$ tấm gỗ thẳng đứng với các chiều cao khác nhau. Chiều cao của tấm gỗ thứ $i$ là $h_i$ ($1 \le h_i \le n$). Ban đầu, tất cả các chiều cao đều phân biệt.

Để thiết kế lại hàng rào, Fred sẽ chọn một đoạn liên tiếp $[l \dots r]$ các tấm gỗ và "làm phẳng" chúng bằng cách cắt bớt để tất cả các tấm trong đoạn đó có chiều cao bằng với chiều cao nhỏ nhất trong đoạn đó. Cụ thể hơn, chiều cao mới của các tấm trong đoạn trở thành $h'_i = \min\{h_l, h_{l+1}, \dots, h_r\}$ với mọi $l \le i \le r$.

Fred có thể thu được bao nhiêu thiết kế hàng rào khác nhau bằng cách áp dụng quy trình này một vài lần (có thể là 0 lần)? Vì kết quả có thể rất lớn, bạn cần in ra kết quả theo modulo $10^9 + 7$.

Hai thiết kế $A$ và $B$ được coi là khác nhau nếu tồn tại ít nhất một tấm gỗ có chiều cao khác nhau giữa $A$ và $B$.

Dữ liệu vào

Dòng đầu tiên chứa $n$ ($1 \le n \le 3\,000$), số lượng tấm gỗ trên hàng rào của Fred.

Dòng thứ hai chứa $n$ số nguyên phân biệt $h_i$ ($1 \le h_i \le n$, $1 \le i \le n$), là chiều cao của mỗi tấm gỗ.

Dữ liệu ra

In ra một số nguyên duy nhất là số lượng các thiết kế hàng rào khác nhau có thể thu được, theo modulo $10^9 + 7$.

Ví dụ

Dữ liệu vào 1

3
1 3 2

Dữ liệu ra 1

4

Dữ liệu vào 2

5
1 2 3 4 5

Dữ liệu ra 2

42

Dữ liệu vào 3

7
1 4 2 5 3 6 7

Dữ liệu ra 3

124