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