The school year has just started, and Edward has found out why Allen isn't in class sometimes. This year, he finally has Latin class with Allen and wants to sit next to him. In the classroom, there are ~N~ students seated in a line, the ~i^\text{th}~ student from the left having height ~h_i~. At the start of every day, Mr. Carswell will partition all ~N~ students into any number of contiguous non-empty groups. However, being the naughty student he is, Allen will only show up to class if the maximum height of each group forms a non-descending sequence.

Please help Edward find the number of partitions of students that satisfy the given condition modulo ~10^9+7~.

Constraints

For this problem, you will NOT be required to pass the sample cases in order to receive points. In addition, all subtasks are disjoint, and you are NOT required to pass previous subtasks to earn points for a specific subtask.

For all subtasks:

~1 \le N \le 10^5~

~1 \le h_i \le 10^9~

Subtask 1 [15%]

~1 \le N \le 21~

Subtask 2 [25%]

~1 \le h_i \le 100~

Subtask 3 [60%]

No additional constraints.

Input Specification

The first line contains an integer ~N~, the number of students.

The next line contains ~N~ integers ~h_i~ ~(1 \le i \le N)~, the heights of the students.

Output Specification

Output one integer, the number of partitions that satisfy the given condition modulo ~10^9+7~.

Sample Input 1

3
2 1 2

Sample Output 1

3

Explanation for Sample 1

The three valid partitions (each represented by a set of ranges) are: ~\{[1, 1], [2, 3]\}, \{[1, 2], [3, 3]\}, \{[1, 3]\}~.

Note that the partition ~\{[1, 1], [2, 2], [3, 3]\}~ is invalid since the sequence formed by the maximum height in each group is not non-descending.

Sample Input 2

5
1 3 7 4 7

Sample Output 2

12