== include(page="template/taskheader" task_id="unuzero") ==

Poveste şi cerinţă...

p<>. 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 &le; q)$.
 
h2. Cerinţă
 
p<>. 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.

h2. Date de intrare

Fişierul de intrare $unuzero.in$ ...

p<>. Fişierul de intrare $unuzero.in$ conţine pe prima linie numărul natural N, iar pe cea de a doua linie numerele naturale $p$ şi $q (p &le; q)$, separate printr-un spaţiu.

h2. Date de ieşire

În fişierul de ieşire $unuzero.out$ ...

p<>. Fişierul de ieşire $unuzero.out$ va conţine pe prima linie numărul natural $K$ cerut.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 &le; p &le; q < N < 1 000 000$.
* Pentru $20%$ din teste $N &le; 25$, iar pentru alte $40%$ din teste $25 < N &le; 1000$.

h2. Exemplu

table(example). |_. unuzero.in |_. unuzero.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...

table(example). |_. unuzero.in |_. unuzero.out |_. Explicaţie |
| 5
2 3
| 8
| 0000110
0001100
0001110
0011000
0011100
0110000
0110110
0111000
|

== include(page="template/taskfooter" task_id="unuzero") ==

7735