Page Contents

*Consecutive Wins SOLUTION*

You are given integers n and k. Given that n represents the number of games you will play, return the number of ways in which you win k or less games consecutively. Mod the result by 10 ** 9 + 7.

Constraints

n ≤ 10,000

k ≤ 10

Example 1

Input

n = 3

k = 2

Output

7

Explanation

Here are the ways in which we can win 2 or fewer times consecutively:

“LLL”

“WLL”

“LWL”

“LLW”

“WWL”

“LWW”