League of Legends (Large)

Time limit3sMemory limit256 MB

Summary

Count the sequences of skills A (1 second) and B (M seconds) that fill exactly N seconds with no idle time, modulo 1e9+7.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics, Math
Solved: No attempts yet

Problem

Gyu-hwan likes a game called League of Legends. In this game, a fight lasts N seconds, and the character Gyu-hwan plays can use two skills, A and B. Skill A takes 1 second to cast, and skill B takes M seconds to cast. Gyu-hwan wants to see every possible skill combination because he likes variety. A skill cannot be used during the casting time of another skill, and there must be no idle time.

For example, if N is 4 seconds and M is 2 seconds, the possible skill combinations are AAAA, AAB, ABA, BAA, and BB, five in total.

Input

The first line gives the fight time N and the casting time M of skill B. (N is a positive integer at most 1018, and M is a positive integer between 2 and 100.)

Output

Print the number of possible combinations modulo 1,000,000,007.

Examples2

Example 1
Input
```
4 2
```
Expected output
```
5
```
Example 2
Input
```
3 2
```
Expected output
```
3
```