Erasing a Permutation

You are given a permutation a_1..N of length N. You can perform the following operation arbitrarily many times (including zero):

• Choose any two adjacent numbers and delete the larger one.

Note that when some numbers between two elements have been deleted, the remaining numbers become adjacent. Determine the number of distinct final sequences that can be obtained by performing a sequence of such operations. Since the answer can be large, output it modulo \(10^9+7\).

Example. Consider the permutation 4 1 3 2 (with N = 4). One possible sequence of operations is:

1. Start with (4, 1, 3, 2).
2. Choose the adjacent pair (4, 1). Since 4 > 1, delete 4 to get (1, 3, 2).
3. Now choose the pair (1, 3). Since 3 > 1, delete 3 to get (1, 2).
4. Finally, choose (1, 2) and delete 2 to get (1).

However, by choosing different adjacent pairs at each step (or stopping earlier), other final sequences (of various lengths) may be obtained. For the above example, the distinct final sequences are:

• (4, 1, 3, 2) – by doing nothing.
• (1, 3, 2)
• (4, 1, 2)
• (1, 2)
• (4, 1)
• (1)

Thus the answer is 6.

inputFormat

The first line contains an integer N (1 ≤ N ≤ 10) denoting the length of the permutation.

The second line contains N distinct integers a₁, a₂, ..., a_N – a permutation of the numbers from 1 to N.

outputFormat

Output one integer — the number of distinct final sequences that can be obtained, modulo \(10^9+7\).

sample

2
1 2

2