Dano je \(n\) brojeva \(x_i\), i tim redom ih ubacujete u binarno stablo pretraživanja (BST). Vaš zadatak je ispisati koliko različitih nizova je moglo dati ovo binarno stablo pretraživanja koje ste dobili. Budući da broj nizova može biti jako velik, ispišite ga modulo \(10^9 + 7\).

Ulaz

U prvom retku nalazi se broj \(n\), \((1 \leq n \leq 2 \cdot 10^5)\). U sljedećem retku nalazi se \(n\) različitih brojeva \(x_i\), \((1 \leq x_i \leq 10^9)\), brojeve koje tim redom morate ubaciti u BST.

Izlaz

Ispišite jedan broj, s koliko različitih nizova možete dobiti to binarno stablo pretraživanja modulo \(10^9 + 7\). U taj broj uključite i dani niz.

U \(50%\) testnih primjera će vrijediti \(n \leq 2000\).

U \(80%\) testnih primjera će dubina stabla biti \(O(\log n)\).

Ulaz primjera

4
1 2 3 4

Izlaz primjera

1

Ulaz primjera

8
5 2 3 1 100 6 8 7

Izlaz primjera

70

Ulaz primjera

15
8 4 12 2 6 10 14 1 3 5 7 9 11 13 15

Izlaz primjera

21964800