Sau khi bị Kanako cho ăn đập vì hệ thống cáp treo 1 chiều thì Kawashiro tiếp tục phải xây một hệ thống khác. Từ Nhân thôn đến Đền Moriya có ~n~ đỉnh núi cạnh nhau. Kawashiro cần chọn ra nhiều nhất số lượng số đỉnh núi sao cho độ cao của nó tăng chặt. Hỏi có bao nhiêu cách để cô có thể hoàn thành công việc?

Input

• Dòng đầu tiên gồm số tự nhiên ~n \le 10^5~.
• Dòng tiếp theo gồm ~n~ số tự nhiên ~a_i \le 10^9~ là độ cao của các đỉnh núi.

Output

• Số lượng cách chọn các đỉnh núi module ~10^9+7~

Sample Test

Input:

6
1 1 2 2 3 3

Output:

8