Rezolvare PBinfo #1656

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ța

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 ≤ 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 ≤ p ≤ q < N < 1.000.000
• Pentru 20% din teste N ≤ 25, iar pentru alte 40% din teste 25 < N ≤ 1000.

Exemplu:

unuzero.in

5
2 3

unuzero.out

8

Explicație

0000110
0001100
0001110
0011000
0011100
0110000
0110110
0111000