Se consideră un şir format din N+2 cifre binare, care conţine cel puţin o cifră 1 şi cel puţin trei cifre 0; prima şi ultima cifră a şirului sunt 0.
Numim 1-secvenţă o succesiune formată numai din cifre 1, aflate pe poziţii consecutive în acest şir, delimitată de câte o cifră 0.
Corina construieşte un astfel de şir, în care numărul de cifre 1 ale fiecărei 1-secvenţe să fie cuprins între două numere naturale date, p şi q (p ≤ q).

Cerinţă

Scrieţi un program care să determine un număr natural K, egal cu restul împărţirii la 666013 a numărului de şiruri distincte, de tipul celui construit de Corina.

Date de intrare

Fişierul de intrare unuzero.in conţine pe prima linie numerele naturale N p q, separate prin câte un spaţiu.

Date de ieşire

Fişierul de ieşire unuzero.out va conţine o sngură linie pe care va fi scris numărul natural K cerut.

Restricţii

• 1 ≤ p ≤ q < N < 1000000

Exemple

unuzero.in	unuzero.out	Explicaţii
5 2 3	8	0000110 0001100 0001110 0011000 0011100 0110000 0110110 0111000

autor: Prof. Gheorghe Manolache

propunător: Prof. Emanuela Cerchez

Colegiul Naţional ″Emil Racoviţă″

emanuela.cerchez@gmail.com