unuzero

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 \leq 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 numărul natural $N$, iar pe cea de a doua linie numerele naturale $p$ şi $q$ ($p \leq q$), separate printr-un spaţiu.

Date de ieșire

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

Restricții și precizări

• $1 \leq p \leq q < N < 1 \ 000 \ 000$
• Pentru $20$% din teste $N \leq 25$, iar pentru alte $40$% din teste $25 < N \leq 1 \ 000$.

Exemplu

unuzero.in

5
2 3

unuzero.out

8

Explicație

$0 \ 0 \ 0 \ 0 \ 1 \ 1 \ 0 \\ 0 \ 0 \ 0 \ 1 \ 1 \ 0 \ 0 \\ 0 \ 0 \ 0 \ 1 \ 1 \ 1 \ 0 \\ 0 \ 0 \ 1 \ 1 \ 0 \ 0 \ 0 \\ 0 \ 0 \ 1 \ 1 \ 1 \ 0 \ 0 \\ 0 \ 1 \ 1 \ 0 \ 0 \ 0 \ 0 \\ 0 \ 1 \ 1 \ 0 \ 1 \ 1 \ 0 \\ 0 \ 1 \ 1 \ 1 \ 0 \ 0 \ 0$