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 students seated in a line, the student from the left having height . At the start of every day, Mr. Carswell will partition all 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 .
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:
Subtask 1 [15%]
Subtask 2 [25%]
Subtask 3 [60%]
No additional constraints.
The first line contains an integer , the number of students.
The next line contains integers , the heights of the students.
Output one integer, the number of partitions that satisfy the given condition modulo .
Sample Input 1
3 2 1 2
Sample Output 1
Explanation for Sample 1
The three valid partitions (each represented by a set of ranges) are: .
Note that the partition 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