Gradina

Problemă

Probabil deja îl știți pe Manole… Acesta de-a lungul anilor a făcut investiții foarte bune, iar acum la bătrânețe, a reușit să își cumpere o grădină de lungime $N$. Chiar dacă este la pensie, acesta este foarte activ, iar acum dorește să își amenajeze un rând continuu de flori pe toată lungimea grădinii.

Acesta are la dispoziție semințe pentru straturi de flori care, odată crescute, ocupă lungimi de $1, 2, \dots, T$

Atenție! Pentru a avea o grădină cât mai diversă, Manole dorește să planteze cel puțin un strat din fiecare lungime disponibilă

Cerință

Ajutați-l pe Manole să calculeze numărul total de posibilități de a amenaja rândul de flori pe lungimea $N$ cu straturi de lungimi $1, 2, \dots, T$ respectând cerința acestuia, de a avea cel puțin un strat din fiecare lungime posibilă.

Date de intrare

In fisierul de intrare gradina.in se găsesc două numere întregi:
Pe prima linie $N$, reprezentând lungimea grădinii lui Manole
Pe a doua linie $T$, reprezentând lungimea maximă a unui strat de flori.

Date de ieșire

Programul va afișa în fișierul gradina.out, un singur număr natural, reprezentând numărul total de posibilități prin care Manole își poate finaliza proiectul, respectând condiția de a folosi cel puțin câte un element de fiecare lungime (de la $1$ la $T$), modulo $10^9 + 7$.

Restricții și precizări

• $1 < T \le 10$
• $5 < N < 20$ – Pentru 20 puncte
• $20 < N < 5000$ – Pentru 50 puncte
• $5000 < N < 10^{10}$ – Pentru 30 puncte
• Restricție: $(1+2+\dots+T) \le N$
• Rezultatul afișat va fi numărul total de posibilități modulo $10^9 + 7$

Exemplul 1

gradina.in

7
3

gradina.out

12

Explicație

Configuratiile posibile sunt:
1 3 2 1
1 2 3 1
1 2 1 3
1 3 1 2
1 1 2 3
1 1 3 2
2 3 1 1
2 1 3 1
2 1 1 3
3 2 1 1
3 1 2 1
3 1 1 2

Exemplul 2

gradina.in

1500
10

gradina.out

625478324

Exemplul 3

gradina.in

1234567
10

gradina.out

535905755