La o şcoală de informatică bine cotată se organizează un concurs de programare. Una dintre problemele de concurs este cea a generării tuturor subşirurilor de lungime maximă pentru un şir cu n elemente. Autorul problemei a hotărât să genereze teste, folosind numai elemente întregi dintr-un interval dat [a,b], iar numărul de soluţii să crească gradat de la un test la altul. Pentru acest motiv el este dornic să afle cazul cel mai nefavorabil existent pentru un interval dat: adică să găsească elemente pentru şir din intervalul [a,b], astfel încât să se obţină un număr maxim de subşiruri de lungime maximă (cu alte cuvinte: niciun alt şir cu elemente din intervalul dat să nu conţină mai multe soluţii de lungime maximă).
De exemplu, pentru n=4, cu elementele intervalului [3,5] putem construi printre altele şirurile a=(a1,a2,a3,a4)=(4,3,4,5) sau b=(b1,b2,b3,b4)=(4,3,5,5). Observăm că şirul a conţine un singur şir crescător de lungime maximă (a2,a3,a4)=(3,4,5), pe când şirul b conţine patru subşiruri crescătoare de lungime maximă, chiar dacă ele sunt de lungime mai mică: (b1,b3)=(4,5), (b1,b4)=(4,5), (b2,b3)=(3,5), (b2,b4)=(3,5).
Cerinţă
Scrieţi un program care să determine pentru n, a şi b date numărul maxim de subşiruri de lungime maximă ce poate avea un şir de lungime n având toate elementele din intervalul
[a,b].
Date de intrare
Fişierul de intrare ssmax.in
conţine pe prima linie trei numere naturale n, a şi b separate prin câte un spaţiu, cu semnificaţiile de mai sus.
Date de ieşire
Fişierul de ieşire ssmax.out
va conţine o singură linie pe care va fi scris un numărul maxim de subşiruri ce se pot construi pentru datele de intrare modulo 666013.
Restricţii
1 <= n, a, b <= 2 000 000 000
Pentru 50% din teste n<120. Pentru aceste valori datele de ieşire nu depăşesc 19 de cifre.