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

Poveste şi cerinţă...

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

h2. Date de ieşire

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.

În fişierul de ieşire $maxmaxmax.out$ ...

h2. Restricţii

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

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. maxmaxmax.in |_. maxmaxmax.out |

| 4 3 5
| 20

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

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