maxmaxmax

Maxmaxmax

== include(page="template/taskheader" task_id="maxmaxmax") ==

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ă.

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 conţine pe prima linie cele 3 numere naturale n, x şi y separate prin spaţiu.

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

h2. Restricţii

1 <= n, x, y <= 1 000 000 000

* $1 ≤ n, x, y ≤ 1 000 000 000$

h2. Exemplu

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.

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") ==

9055