The most difficult part of the jury’s work, besides coming up with problems, writing correct solutions, creating checkers, validators, tests, statements, and editorials, is arranging the problems among themselves in an already prepared set. Nobody knows how to do it correctly, so an ancient technique is used for this.

This secret knowledge consists of a simple algorithm:

1. First, each problem in the set is sorted by difficulty, with the most difficult one assigned 1, the second most difficult assigned 2, and so on.
2. Then a template is taken — some permutation of numbers from 1 to N, where N is the number of problems in the contest, which determines the arrangement of problems by difficulty.
3. After that, a left subtemplate and a right subtemplate are found. To do this, the position of the most difficult problem is determined in the template. Then the left subtemplate is the subtemplate responsible for all the problems that come before the most difficult one (if the most difficult problem was the first in the template, it becomes empty), and the right subtemplate is the subtemplate responsible for all the problems that come after the most difficult one (if the most difficult problem was the last in the template, it also becomes empty).
4. Two templates are called equivalent if they are both empty, or if the position of the most difficult problem is the same in both templates, their left subtemplates are equivalent, and their right subtemplates are also equivalent.
5. And the final step for arranging the problems in the contest is to choose an arbitrary template equivalent to the one given initially.

There is one problem with this. The jury always used the same ancient template, and it is time to change it, but to do that, the number of templates equivalent to it needs to be calculated. The jury is currently busy rearranging problems in another contest and answering participants’ questions, so this task falls to you.

The first line contains a single integer N — the number of problems in the set (1 ≤ N ≤ 10⁵).

The second line contains N integers p_i separated by spaces — the description of the template you are checking (1 ≤ p_i ≤ N, all p_i are distinct).

Print the number of templates equivalent to the given one, modulo 10⁹+7. In other words, find the remainder when the number of templates is divided by 1 000 000 007.

In the first example, there are only two templates equivalent to the input template — (2,1,3) and (3,1,2).