== include(page="template/taskheader" task_id="w") ==
Poveste și cerință...
Un vector de numere se numește **de formă W** dacă întrunește următoarele condiții:
# Este format din patru segmente în ordine descrescătoare, în ordine crescătoare, în ordine descrescătoare, în ordine crescătoare.
# Ordonarea nu este strictă, deci segmentele crescătoare și descrescătoare pot include elemente consecutive egale.
# Oricare două segmente consecutive au un capăt comun.
# 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 $(3 1), (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 $(3 1), (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.
h2. Date de intrare
Fișierul de intrare $w.in$ ...
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.
h2. Date de ieșire
În fișierul de ieșire $w.out$ ...
Î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.
h2. 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.
h2. Exemplu
table(example).
|_. w.in |_. w.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
...
|_. w.in |_. w.out |_. Explicație |
| 5
3 1 4 2 3
| 6
| Cele 6 permutări de formă W sunt:
$3 1 3 2 4$
$3 1 4 2 3$
$3 2 3 1 4$
$3 2 4 1 3$
$4 1 3 2 3$
$4 2 3 1 3$
|
| 7
1 2 2 2 3 4 4
| 48
| ⠀
|
== include(page="template/taskfooter" task_id="w") ==
