Magical Frog
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 2Sample Output
3Sample Input
6 3Sample Output
24Sample Input
2 2Sample Output
2
Comments
:OOO IT HAS MY NAME ON IT !!!!!
hello, please add the samples as tests because there are some accepted solutions but produce wrong answers in the samples, thank you.