Fişierul intrare/ieşire:	maxmaxmax.in, maxmaxmax.out	Sursă	Lot Baia Mare 2013 - Baraj 1 Seniori
Autor	Dragos Oprica, Zoltan Szabo	Adăugată de	Daniel Constantin Anghel •Magnvs
Timp execuţie pe test	0.03 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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

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.

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.

Restricţii

• 1 ≤ n, x, y ≤ 1 000 000 000

Exemplu

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

Cum se trimit solutii?