== include(page="template/taskheader" task_id="drumuri") ==
Poveste și cerință...
Care este numărul maxim de drumuri optime (drumuri cu număr minim de arce) care pot exista între două vârfuri ale unui graf orientat cu N vârfuri?
h2. Date de intrare
Fișierul de intrare $drumuri.in$ ...
Fișierul de intrare $drumuri.in$ conține un singur număr natural N.
h2. Date de ieșire
În fișierul de ieșire $drumuri.out$ ...
În fișierul de ieșire $drumuri.out$ se va scrie un singur număr D reprezentând restul la împărțirea cu 9001 al numărului maxim de drumuri optime care pot exista între două vârfuri ale unui graf orientat cu N vârfuri.
h2. Restricții
* $... ≤ ... ≤ ...$
* 2 ≤ N ≤ 10[^18^]
h2. Exemplu
table(example).
|_. drumuri.in |_. drumuri.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6
| 4
|
h3. Explicație
...
Fie graful orientat G cu vârfurile {1, 2, 3, 4, 5, 6} și arcele {(1,2), (1,3), (1,4), (1,5), (2,6), (3,6), (4,6), (5,6)}. Între vârfurile 1 și 6 există 4 drumuri optime (fiecare dintre acestea format din câte 2 arce): (1, 2, 6), (1, 3, 6), (1, 4, 6), (1, 5, 6). Acesta este numărul maxim de drumuri optime care pot exista între două vârfuri ale unui graf orientat cu 6 vârfuri.
== include(page="template/taskfooter" task_id="drumuri") ==
