769. Climb Stairs with K Steps (Modulo 10^9+7)

You are climbing a staircase of n steps. On each move, you may climb any number of steps from 1 up to k. Return the total number of DISTINCT ways to reach the top, taken modulo 10^9 + 7. By convention, there is exactly 1 way to be at the top when n = 0 (do nothing). Implement with recursion + memoization.

Input: Two non-negative integers n and k separated by a comma.

Output: Return an integer equal to the count mod (10^9 + 7).

Examples

Input: 4, 2
Output: 5
Explanation: Standard climb stairs with steps 1 or 2 -> Fibonacci count = 5.

Input: 3, 3
Output: 4
Explanation: Steps 1, 2, 3 -> 1+1+1, 1+2, 2+1, 3.

Input: 0, 2
Output: 1
Explanation: Base case: already at the top.

Constraints

• 0 <= n <= 1000
• 1 <= k <= 10

Asked by