Rezolvare PBinfo #4504

Cerința

Se dau numerele naturale n, p și q. Să se determine numărul șirurilor de n biți în care numărul biților de 1 este cuprins între p și q. Pentru că acest număr poate fi foarte mare, se va determina modulo 1.000.000.007.

Date de intrare

Programul citește de la tastatură n, p și q.

Date de ieșire

Programul va afișa pe ecran numărul X, reprezentând numărul șirurilor de n biți în care numărul biților de 1 este cuprins între p și q, modulo 1.000.000.007.

Restricții și precizări

• 3 ≤ n ≤ 1.000.000
• 0 ≤ p < q ≤ n
• q - p ≤ 5
• 1.000.000.007 este număr prim

Exemplu:

Intrare

4 2 3

Ieșire

10

Explicație

Șirurile sunt: 0011, 0101, 0110, 1001, 1010, 1100, 0111, 1011, 1101, 1110