G. Permutation Removal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Amir has a permutation of $$$1$$$ to $$$n$$$, where $$$n$$$ is an even number. In each step, Amir selects two adjacent elements of the array, whose the number on the left side is greater than the number on the right side, then removes both and pastes the remaining numbers of the array together.

Now Amir wants to find the number of ways to remove all permutation's elements. Since the number of ways may be too large, Amir asks you to find the answer for him and print the answer modulo $$$10^9 + 7$$$.

Input

In the first line of input, $$$n$$$ is given which $$$n$$$ is even.

$$$2 \le n \le 500$$$.

In the second line of input you'll be given a permutation of $$$1$$$ to $$$n$$$.

Output

Print the answer modulo $$$10^9 + 7$$$.

Example
Input
6
6 4 3 2 1 5
Output
3
Note

In the first sample we have $$$3$$$ ways of removing the arrays' elements :

$$$[6, 4, 3, 2, 1, 5] \rightarrow [6, 2, 1, 5] \rightarrow [6, 5] \rightarrow []$$$

$$$[6, 4, 3, 2, 1, 5] \rightarrow [6, 4, 1, 5] \rightarrow [6, 5] \rightarrow []$$$

$$$[6, 4, 3, 2, 1, 5] \rightarrow [6, 4, 3, 5] \rightarrow [6, 5] \rightarrow []$$$