Cho ~a = a_1, a_2, \dots, a_n~ là một dãy số nguyên không âm. Hãy đếm số cách chia dãy ~a~ thành các đoạn con liên tiếp, sao cho ~\text{MEX}~ của các đoạn con, theo thứ tự, tạo thành một dãy không giảm. Ở đây, ~\text{MEX}~ của đoạn con ~[i..j]~ là số nguyên không âm nhỏ nhất không xuất hiện trong ~{a_i, a_{i + 1}, \dots, a_j}~.

Input Specification: Data taken from SMEX.INP

• Dòng đầu tiên chứa số nguyên dương ~n~ ~(n \le 5000)~.
• Dòng tiếp theo là ~n~ số nguyên ~a_1, a_2, \dots, a_n~ ~(a_i \le 10^9)~.

Output Specification: Data written in SMEX.OUT

• Một dòng duy nhất là kết quả bài toán. Vì kết quả có thể rất lớn nên chỉ cần in phần dư của số cách tìm được khi chia cho ~10^9 + 7~.

Subtasks

• Subtask #1 [25%]: ~n \le 1000~.
• Subtask #2 [25%]: ~a_i \le 100~.
• Subtask #3 [25%]: ~n \le 2000~.
• Subtask #4 [25%]: Không có giới hạn gì thêm

Sample Cases

Input #1:

8
3 0 2 1 0 1 3 2

Output #2:

8