An automated packaging system is responsible for packing boxes. A box is certified to hold a certain weight. Given an integer total, calculate the number of possible ways to achieve the total as a sum of weights of items weighing integers from 1 to k, inclusive.

Relevant Citadel OA Problems:

Triplets

Ways to Sum

Consecutive Sum

Disk Space Analysis

Do They Belong?

Global Maximum

Initial Public Offering

Inversions

Portfolio Balances

Prime Factor Visitation

Profit Targets

Sprint Training

Throttling Gateway

Birthday Card Collection

Parameter

total: the value to sum to

k: the maximum of the range of integers to consider when summing to total

Result

the number of ways to sum to the total; the number might be very large, so return the integer modulo 1000000007(10^9+7)

Example

Input: total = 8, k = 2

To reach a weight of 8, there are 5 different ways that items with weights between 1 and 2 can be combined:

[1,1,1,1,1,1,1,1]

[1,1,1,1,1,1,2]

[1,1,1,1,2,2]

[1,1,2,2,2]

[2,2,2,2]

Output: 5