Se tiene una permutación de \(1, \dots, n\). Insertando sus valores en orden en un árbol binario de búsqueda vacío se obtiene un árbol. Cuenta cuántos otros órdenes de los mismos valores producen exactamente el mismo árbol (el orden original no cuenta).

Entrada

La primera línea tiene \(n\) \((1 \le n \le 1000)\). La segunda tiene la permutación.

Salida

La cantidad, módulo \(10^9 + 7\).

Ejemplo 1

Entrada

3
2 1 3

Salida

1

Ejemplo 2

Entrada

5
3 4 5 1 2

Salida

5

Ejemplo 3

Entrada

3
1 2 3

Salida

0