Wooden Signs

A carpenter received an order for a wooden directional sign. The sign is built from arrow shaped boards stacked from the bottom to the top. Every board must be aligned vertically with the board below it, either to the basis of the arrowhead below or to the opposite end, and it is fixed there with a specially designed screw. Two neighbouring boards must overlap.

The carpenter wrote down a sequence of integers to encode the sketch the designer sent, but the sequence does not determine a single model, and he already threw the original sketch away. What looked like a trivial task turned into a big jigsaw for him.

The sequence has $1 + N$ elements and encodes the $N$ arrows of the sign from the bottom to the top. The first element is the position of the left side of the bottom arrow. The remaining $N$ elements give the positions where the arrowheads start, from the bottom to the top: the $i$-th of them is the position of the $i$-th arrowhead basis. For instance, both signs in the picture, the left one and the right one, can be encoded by 2 6 5 1 4.

Because a board must be aligned vertically with the previous one, either to the basis of the previous arrowhead or to the opposite side, if the sequence were 2 6 5 1 4 3, then in either of the signs shown the fifth arrow could be fixed with a screw at 1 pointing to the right, or with a screw at 4 pointing to the left, with the arrowhead basis at 3.

If the sequence were 2 3 1, the second arrow could only be fixed with a screw at 3, pointing to the left, because consecutive boards must overlap.

All arrowheads are alike. The designer told the carpenter that the arrowhead bases stand on different vertical lines, together with the left side of the bottom arrow, and that all of them form a permutation of $1$ to $N+1$. That is why the carpenter left out the details and wrote down only the permutation, for example 2 6 5 1 4 3.

Given the sequence the carpenter wrote down, compute how many directional signs can be crafted. The number can be very large, so print it modulo $2^{31} - 1 = 2147483647$. The second integer of the sequence is always greater than the first one, since the bottom arrow always points to the right.

The first line has one integer $N$. The second line contains a permutation of the integers from $1$ to $N+1$. Integers on the same line are separated by a single space.

Print a single line with the number of distinct signs that the given permutation can describe, modulo $2^{31} - 1 = 2147483647$.

• $1 \le N < 2000$, the number of arrows