== include(page="template/taskheader" task_id="dag") ==
Poveste şi cerinţă...
Un *graf aciclic orientat* (DAG - Directed Acyclic Graph) este un graf orientat fără cicluri.
Fie <tex>G</tex>un graf orientat aciclic simplu (adică nu conţine muchii multiple între aceleaşi noduri sau muchii de la un nod la el însuşi) în care nodurile sunt etichetate cu primele $N$ numere naturale.
O sortare topologică a nodurilor unui graf aciclic orientat <tex>G</tex> este o ordonare a nodurilor astfel încât, dacă există un arc <tex>(i, j) \in G</tex>, atunci $i$ apare înaintea lui $j$ în această ordonare. O astfel de ordonare se poate reprezenta ca o permutare <tex>P</tex> a etichetelor nodurilor grafului <tex>G</tex>.
Dintre toate sortările topologice ale unui graf, numim sortarea topologică minimă lexicograf acea sortare topolologică a cărei permutare este mai mică lexicografic decât permutarea oricărei alte sortări topologice.
O permutare <tex>a_1, a_2, ..., a_N</tex> este mai mică lexicografic decât o altă permutare <tex>b_1, b_2, ..., b_N</tex>, dacă există un număr întreg $S$ mai mic sau egal cu $N$ astfel încât <tex>a_1 = b_1, a_2 = b_2, ..., a_{S-1} = b_{S-1}</tex>, iar <tex>a_S < b_S</tex>.
h2. Cerinţă
Se dă o permutare <tex>P</tex> de lungime $N$. Câte grafuri orientate aciclice etichetate cu primele $N$ numere naturale au proprietatea că <tex>P</tex> este sortarea lor topologică minimă lexicografic?
h2. Date de intrare
Fişierul de intrare $dag.in$ ...
În fişierul $dag.in$ se află pe prima linie numărul $N$. Pe a doua linie se vor afla $N$ numere distincte cu valori între $1$ şi $N$ reprezentând permutarea <tex>P</tex>.
h2. Date de ieşire
În fişierul de ieşire $dag.out$ ...
În fişierul $dag.out$ trebuie să se găsească un singur număr care reprezintă numărul de grafuri orientate aciclice de $N$ noduri pentru care <tex>P</tex> este sortarea lor topologică minimă lexicografic. Deoarece această valoare poate fi foarte mare, se cere să afişaţi doar restul modulo $1.000.000.007$ al acesteia.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 200.000;$
* Pentru teste în valoare de 10 puncte, $N ≤ 6;$
* Pentru alte teste în valoare de 55 puncte, $N ≤ 2.500.$
h2. Exemplu
table(example). |_. dag.in |_. dag.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
| 3
3 1 2
| 3
|
| 10
1 2 3 5 4 6 7 8 10 9
| 92960636
|
h3. Explicaţie
...
În primul exemplu există 3 grafuri orientate aciclice simple cu $3$ noduri a căror sortare topologică minimă este <tex>P_1 = 3; P_2 = 1; P_3 = 2</tex>.
== include(page="template/taskfooter" task_id="dag") ==
