== include(page="template/taskheader" task_id="maxmaxmax") ==
Poveste şi cerinţă...
Maximilian a învăţat programare dinamică la şcoală şi şi-a fixat scopul nobil de a ajunge în Lotul Naţional de Informatică şi, dacă se poate, chiar în cel restrâns. Nu demult a învăţat algoritmul ce calculează pentru un şir cu $n$ elemente, un subşir strict descrescător de lungime maximă.
Aceasta fiind o problemă uşoară, a modificat enunţul problemei şi acum nu mai ştie să o rezolve. Problema sună în felul următor: ştiind că cele $n$ elemente ale şirului pot avea valori din mulţimea {$x$, $x+1$, ... , $y$}, să se determine numărul şirurilor distincte ce admit un număr maxim de subşiruri strict descrescătoare de lungime maximă.
Cunoscând valorile $n$, $x$ şi $y$ cu semnificaţiile de mai sus, ajutaţi-l pe Maximilian să calculeze numărul de şiruri distincte modulo $1114111$ ce conţin un număr maxim de subşiruri strict descrescătoare de lungime maximă.
h2. Date de intrare
Fişierul de intrare $maxmaxmax.in$ ...
Fişierul de intrare maxmaxmax.in conţine pe prima linie cele $3$ numere naturale $n$, $x$ şi $y$ separate prin spaţiu.
h2. Date de ieşire
În fişierul de ieşire $maxmaxmax.out$ ...
Fişierul de ieşire maxmaxmax.out va conţine pe prima linie un singur număr natural ce reprezintă numărul şirurilor distincte modulo 1114111.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ n, x, y ≤ 1 000 000 000$
h2. Exemplu
table(example). |_. maxmaxmax.in |_. maxmaxmax.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4 3 5
| 20
|
h3. Explicaţie
...
Sunt 5 şiruri cu un număr maxim de 4 soluţii, ce admit subşir descrescător de lungime maximă $2$:
$(4 4 3 3) (4 5 3 3) (5 5 3 3) (5 5 3 4) (5 5 4 4)$
Sunt alte 15 şiruri cu un număr maxim de 4 soluţii, ce admit subşir descrescător de lungime maximă $1$:
$(3 3 3 3) (3 3 3 4) (3 3 3 5) (3 3 4 4) (3 3 4 5) (3 3 5 5)$
$(3 4 4 4) (3 4 4 5) (3 4 5 5) (3 5 5 5) (4 4 4 4) (4 4 4 5)$
$(4 4 5 5) (4 5 5 5) (5 5 5 5)$
În total $15 + 5 = 20$ de soluţii.
Toate celelalte şiruri permit un număr mai mic de soluţii de lungime maximă.
== include(page="template/taskfooter" task_id="maxmaxmax") ==
