To ensure a better performance at the upcoming party, Xiao A, the leader of the AAA choir, needs to arrange the choir members in a formation based on their heights. Suppose there are $N$ people in the choir, and the height of the $i$-th person is $H_i$ millimeters ($1000 \le H_i \le 2000$). It is known that no two people have the same height.

Suppose the final formation consists of $N$ people standing in a row. To simplify the problem, Xiao A devised the following arrangement method: he lets everyone stand in an initial formation in an arbitrary order, and then inserts each person into the final formation one by one from left to right according to the following rules:

• The first person is inserted directly into the empty current formation.
• For each person starting from the second:
  • If they are taller than the person immediately preceding them in the initial order ($H$ is larger), they are inserted at the rightmost end of the current formation.
  • If they are shorter than the person immediately preceding them in the initial order ($H$ is smaller), they are inserted at the leftmost end of the current formation.

When all $N$ people have been inserted into the current formation, the final formation is obtained.

For example, if there are $6$ people in an initial formation with heights $1850, 1900, 1700, 1650, 1800, 1750$, Xiao A will obtain the final formation through the following steps:

• $1850$
• $1850, 1900$ because $1900 > 1850$
• $1700, 1850, 1900$ because $1700 < 1900$
• $1650, 1700, 1850, 1900$ because $1650 < 1700$
• $1650, 1700, 1850, 1900, 1800$ because $1800 > 1650$
• $1750, 1650, 1700, 1850, 1900, 1800$ because $1750 < 1800$

Therefore, the final formation is $1750, 1650, 1700, 1850, 1900, 1800$.

Xiao A has an ideal formation in mind. He wants to know how many initial formations can result in his ideal formation as the final formation using the aforementioned arrangement method.

Input

The first line of the input is a positive integer $N$, representing the total number of people. The second line contains $N$ positive integers separated by spaces, representing the ideal formation Xiao A has in mind from left to right: $H_1, H_2, \dots, H_N$.

The input data guarantees $1000 \le H_i \le 2000$ and that no two $H$ values are the same. $30\%$ of the data satisfies $1 \le N \le 100$, and $100\%$ of the data satisfies $1 \le N \le 1000$.

Output

Output a single number representing the number of initial formations that can result in the specified ideal formation. Since the number of valid initial formations can be very large, output the result modulo $19650827$.

Examples

Input 1

4
1701 1702 1703 1704

Output 1

8

Note 1

The $8$ initial formations are $(1701, 1702, 1703, 1704)$, $(1704, 1703, 1702, 1701)$, $(1702, 1701, 1703, 1704)$, $(1703, 1702, 1701, 1704)$, $(1702, 1703, 1701, 1704)$, $(1702, 1703, 1704, 1701)$, $(1703, 1704, 1702, 1701)$, and $(1703, 1702, 1704, 1701)$.

Input 2

4
1704 1703 1702 1701

Output 2

0