WCat is playing a covering game.

He has an $n \times n$ grid, where the cell in the $i$-th row and $j$-th column is denoted by $(i, j)$. This grid contains $n$ black cells, and the rest are white cells, such that no two black cells share the same row or the same column.

For every positive integer $k$, WCat has an infinite supply of $1 \times k$ red rectangles and $k \times 1$ blue rectangles. WCat needs to use these rectangles to cover the grid.

In this filling game, red rectangles can only be placed horizontally, and blue rectangles can only be placed vertically. More specifically, for a $1 \times k$ red rectangle, WCat can choose positive integers $i, j$ such that $1 \le i, j+k-1 \le n$, and use this red rectangle to cover the cells $(i, j+l)$ for $l=0, 1, \dots, k-1$. For a $k \times 1$ blue rectangle, WCat can choose positive integers $i, j$ such that $1 \le i+k-1, j \le n$, and use this blue rectangle to cover the cells $(i+l, j)$ for $l=0, 1, \dots, k-1$.

WCat must use the rectangles at his disposal to cover all white cells without overlap, while not covering any black cells. If WCat uses $2n - 2$ rectangles, he wins the game.

Two rectangles are considered identical if they have the same color and cover the same set of white cells; otherwise, two rectangles are different.

WCat wants to know how many covering schemes allow him to win this game. Two covering schemes are different if and only if there exists a white cell that is covered by a different rectangle in the first scheme than in the second. Since the number of schemes can be large, you only need to output the number of schemes modulo $10^9 + 7$.

Input

The first line contains a positive integer $n$ ($2 \le n \le 2 \times 10^5$), representing the side length of the grid.

The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$, representing that the cell in the $i$-th column and $a_i$-th row is a black cell. It is guaranteed that $a_1, a_2, \dots, a_n$ is a permutation of $1, 2, \dots, n$.

Output

Output a single integer representing the number of covering schemes that win the game, modulo $10^9 + 7$.

Examples

Input 1

2
1 2

Output 1

4

Note 1

WCat can only use $1 \times 1$ rectangles to cover the grid, and each rectangle can be either red or blue, so there are $2 \times 2 = 4$ covering schemes.

Input 2

See 2.in and 2.ans in the problem directory.

Output 2

See 2.in and 2.ans in the problem directory.

Input 3

See 3.in and 3.ans in the problem directory.

Output 3

See 3.in and 3.ans in the problem directory.

Input 4

See 4.in and 4.ans in the problem directory.

Output 4

See 4.in and 4.ans in the problem directory.