k-Tree · Interview Problem

Back to problems

Codeforces

Medium

Dynamic Programming

Combinatorics

Math

k-Tree

Count the number of ways to write $n$ as a sum of numbers from $1 $to$ k $, using at least one summand that is$ ge d$.

Acceptance 0%

Start Practice

Problem Statement

Problem

You are given three integers $n$ , $k$ , and $d$ . Count how many ordered sequences of positive integers satisfy all of the following:

The sequence sum is exactly $n$ .
Every element in the sequence is in the range $[1, k]$ .
At least one element in the sequence is at least $d$ .

Because the answer can be large, return it modulo $10^9 + 7$ .

An ordered sequence means that different orders of the same numbers are considered different.

Goal

Compute the number of valid sequences.

Input Format

A single line contains three integers $n$ , $k$ , and $d$ .

Output Format

Print one integer — the number of valid sequences modulo $10^9 + 7$ .

Constraints

$1 \le n \le 100$
$1 \le k \le 100$
$1 \le d \le k$
Answer modulo $10^9 + 7$

Examples

Sample cases returned by the problem API.

Example 1

Input

3 3 2

Output

Explanation

Valid ordered sequences are: [3], [1,2], and [2,1]. The sequence [1,1,1] is invalid because it contains no element at least 2.

Example 2

Input

3 3 3

Output

Explanation

Only [3] works. All other sequences sum to 3 but do not use any element at least 3, except [3] itself.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress