Fișierul intrare/ieșire	w.in, w.out	Sursă	RMI 2018 ziua 2
Autor	Zoltan Szabo	Adăugată de	Tinca Matei • TincaMatei
Timp de execuție pe test	0.6 sec	Limită de memorie	131072 KB
Scorul tău	N/A	Dificultate	N/A

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

W

Un vector de numere se numește de formă W dacă întrunește următoarele condiții:

1. Este format din patru segmente în ordine descrescătoare, în ordine crescătoare, în ordine descrescătoare, în ordine crescătoare.
2. Ordonarea nu este strictă, deci segmentele crescătoare și descrescătoare pot include elemente consecutive egale.
3. Oricare două segmente consecutive au un capăt comun.
4. Orice segment conține cel putin două valori distincte.

De exemplu, vectorul (3 1 2 1 1 4) este în forma de W deoarece este format din segmentele , (1 2), (2 1 1), (1 4). Vectorul (3 1 2 2 2 4) nu are formă de W. Ar putea fi împărțit în segmentele , (1 2), (2 2 2), (2 4), însă segmentul (2 2 2) nu conține două valori distincte.

Dându-se un vector de N întregi, câte permutări ale sale sunt de formă W? Două permutări ale vectorului, (p1 p2 ... pN) și (q1 q2 ... qN), sunt considerate distincte dacă există cel puțin o poziție 1 ≤ i ≤ N pentru care pi ≠ qi. În exemplul de mai sus, permutarea (3 1 2 1 1 4) trebuie numărată o singură dată, deoarece prin permutarea celor trei valori de 1 nu se obțin permutări diferite de ea.

Date de intrare

In fișierul de intrare w.in, prima linie va conține numărul N. A doua linie va conține cele N valori ale vectorului, separate prin spații.

Date de ieșire

În fișierul de ieșire w.out, afișati un singur număr: restul împărțirii la 1.000.000.007 a numărului de permutări distincte de formă W ale vectorului.

Restricții

• 5 ≤ N ≤ 300.000
• Valorile vectorului sunt numere întregi cuprinse între 1 și 1.000.000 inclusiv.
• Pentru 20 de puncte, vor exista doar două valori distincte în cele N elemente.
• Pentru alte 30 de puncte, toate cele N elemente sunt distincte.

Exemplu