maxmaxmax

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, \dots , 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 $1 \ 114 \ 111$ 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 $1 \ 114 \ 111$.

Restricții și precizări

• $1 \leq n, x, y \leq 10^9$;

Exemplul 1

maxmaxmax.in

4 3 5 

maxmaxmax.out

20

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