Magical Frog

Submit solution

Points: 35
Time limit: 1.0s
Memory limit: 256M

Problem type

Reda started this year studying at HogwarIT for magic and technology, his Potions professor insisted that all the students get magical pets to help them with the rest of the course, Reda picked a Frog.

For the first homework, students are required to train their pets to do some math tricks. Reda chose to observe his pet's movement and tried to find some patterns to help him find a suitable trick to teach it.

The frog lived in the HogwarIT dormitory staircase, each day
The frog starts at the bottom of the stairs (i.e, stair number \(0\)) and can jump to any of the next \(K\) stairs, (i.e if frog is at stair \(i\) it can jump to stair \(i + j\) where (\(i + j)\leq N\) and \(1 \leq j \leq K\)) and it keeps doing jumps until it reaches the N'th stair.

Can you help Reda count the number of ways the frog can reach the N'th stair, since this number can be too big output it modulo \(10^{9} + 7\).

Two ways are considered different if the sequence of jumps taken in both of them is different.

Input Specification

The input contains a single line with 2 integers \(1 \leq N \leq 10^{9} \) \(1 \leq K \leq 20\) As described above. Also it is guaranteed that \( K \leq N \).

Output Specification

Print one single line, the number of different ways to reach the N'th stair.

Sample Input

3 2

Sample Output


Sample Input

6 3

Sample Output


Sample Input

2 2

Sample Output



  • 0
    ridars  commented on Aug. 28, 2023, 8:49 p.m.


  • 0
    mouad_smi  commented on June 1, 2022, 2:32 p.m.

    hello, please add the samples as tests because there are some accepted solutions but produce wrong answers in the samples, thank you.