Chặt nhị phân là một kĩ thuật tìm kiếm quen thuộc đối với tất cả các lập trình viên. Một dãy số ~a~ là một dãy có thể chặt nhị phân được nếu như nó là một dãy số đồng biến. Cụ thể hơn, dãy đồng biến là dãy thoả mãn tính chất: ~(a_i - a_j) \cdot (a_j - a_k) \ge 0 \ \ \forall 1 \le i < j < k \le n~. Chú ý rằng theo định nghĩa này, mọi dãy số có không, một hoặc hai phần tử đều là dãy đồng biến.

Cho dãy số ~a_1, a_2, \ldots, a_n~, hãy đếm xem có bao nhiêu dãy con khác nhau của dãy này là dãy đồng biến.

Vì kết quả có thể rất lớn, hãy in ra phần dư của kết quả khi chia cho ~10^9 + 7~.

Một dãy ~b~ được gọi là dãy con của dãy ~a~ nếu như ta có thể bỏ bớt một vài phần tử của ~a~ và giữ nguyên thứ tự của các phần tử còn lại để thu được dãy ~b~.

Hai dãy con được gọi là khác nhau nếu tồn tại một vị trí ~i~ sao cho phần tử thứ ~i~ của dãy ~a~ được bỏ đi để tạo ra dãy con thứ nhất, nhưng không được bỏ đi để tạo ra dãy con thứ hai.

Input

• Dòng đầu chứa số nguyên dương ~n~ ~(1 \le n \le 10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên không âm ~a_1, a_2, \ldots, a_n~ ~(0 \le a_i \le 10^5)~.

Output

• In ra một số nguyên không âm là kết quả của bài toán.

Subtask

• Subtask ~1~ (~20\%~ số điểm): ~n \le 20~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~2~ (~20\%~ số điểm): ~n \le 80~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~3~ (~20\%~ số điểm): ~n \le 300~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~4~ (~20\%~ số điểm): ~n \le 5000~; Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~5~ (~10\%~ số điểm): Dãy ~a~ là một hoán vị của ~n~ số nguyên dương đầu tiên
• Subtask ~6~ (~10\%~ số điểm): Không có ràng buộc gì thêm

Sample input 1

5
4 2 1 5 3

Sample output 1

17

Explaination

Các dãy con đồng biến là:

• []
• [4], [2], [1], [5], [3]
• [4, 2], [4, 1], [4, 5], [4, 3], [2, 1], [2, 5], [2, 3], [1, 5], [1, 3], [5, 3]
• [4, 2, 1]