Hazoq and tax evasion#12215

Hazoq and tax evasion

3 seconds

1,024 megabytes

Very hard

Hazoq was playing Minecraft then his door suddenly came off flying. Turns out it's Joy and he's here to claim taxes. But since Hazoq spent all his money on indomie he was not able to pay them and decided to run. Joy being not able to walk properly because of his old age he had no chance of catching him so he made a deal with Hazoq, Joy gave Hazoq a problem and told him if he solves it he doesn't have to pay taxes anymore.

The problem is as follows:

Given three integers $n$ , $x$ , $k$ count the number of different arrays $a$ of size $m$ that satisfy all the following conditions:

all elements of $a$ are positive integers
$m \leq x$ m \le x.
$\sum_{i = 1}^{m} a_{i} = n$ \sum_{i=1}^m a_i = n.
$max (a_{1}, a_{2}, \dots, a_{m}) - min (a_{1}, a_{2}, \dots, a_{m}) \geq k$ \max(a_1, a_2, \ldots, a_m)-\min(a_1, a_2, \ldots, a_m) \ge k.

You're a friend of Hazoq so you've decided to help him.

As the answer can be very large, output it modulo $1 0^{9} + 7$ 10^9 + 7.

Input

The input consists of only three integers $n, x, k$ n, x, k ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5, $1 \leq x \leq min (500, n)$ 1 \le x \le \min(500, n), $0 \leq k \leq n - 1$ 0 \le k \le n-1).

Output

The output consists of only one integer, the number of different arrays modulo $1 0^{9} + 7$ 10^9 + 7.

Examples

Example 1

Loading

Example 2

Loading

Example 3

Loading

Note

In the first sample. The two arrays are ${1, 4}$ and ${4, 1}$ . It can be shown that there are no other arrays that satisfy the conditions.

In the second sample. The arrays are ${1, 1, 4}$ \{1, 1, 4\}, ${1, 4, 1}$ \{1, 4, 1\}, ${4, 1, 1}$ \{4, 1, 1\}, ${1, 5}$ and ${5, 1}$ .

Scoring

Subtask $1$ ( $20$ points): $1 \leq n \leq 8$ 1 \le n \le 8
Subtask $2$ ( $20$ points): $k = 0$ k=0
Subtask $3$ ( $20$ points): $1 \leq n \leq 100$ 1 \le n \le 100
Subtask $4$ ( $20$ points): $x = 2$ x=2
Subtask $5$ ( $30$ points): $1 \leq n \leq 1000$ 1 \le n \le 1000
Subtask $6$ ( $40$ points): $1 \leq x \leq 20$ 1 \le x \le 20
Subtask $7$ ( $150$ points): No additional constraints

m \leq x

\sum_{i = 1}^{m} a_{i} = n

max (a_{1}, a_{2}, \dots, a_{m}) - min (a_{1}, a_{2}, \dots, a_{m}) \geq k

1 0^{9} + 7

n, x, k

1 \leq n \leq 1 0^{5}

1 \leq x \leq min (500, n)

0 \leq k \leq n - 1

1 0^{9} + 7

{1, 1, 4}

{1, 4, 1}

{4, 1, 1}

1 \leq n \leq 8

k = 0

1 \leq n \leq 100

x = 2

1 \leq n \leq 1000

1 \leq x \leq 20