Phone Friends

Time limit1sMemory limit1024 MB

Summary

Count ordered distributions of K identical candies to N friends where each friend gets between m and M candies, modulo 1e9+7.

Level: Hard8 of 10
Topics: Dynamic programming, Combinatorics, Prefix sum, Math
Solved: No attempts yet

Problem

Yunje, exhausted from delivering candy, came home and went to bed.

In a dream as sweet as candy, Yunje made imaginary friends called "phone friends." Phone friends love candy, but they never ask for a candy delivery. Instead, they come to Yunje directly, so he can just stand still and hand out the candy!

In the dream, Yunje wants to distribute $K$ candies of the same kind among $N$ phone friends, giving out all of them. The phone friends will not leave Yunje no matter how the candy is distributed, but each wants to receive at least $m$ candies. Also, no friend wants anyone other than themselves to receive more than $M$ candies.

Yunje has at least $Nm$ and at most $NM$ candies. Find the number of ways Yunje can distribute the candy while satisfying all the phone friends.

Input

The first line gives the integers $N$ , $m$ , $M$ , $K$ . ( $2 \leq N \leq 1\ 000$ , $0 \leq m \leq M \leq 1\ 000$ , $Nm \leq K \leq NM$ )

$N$ is the number of phone friends and $K$ is the number of candies Yunje has. $m$ is the minimum number of candies each friend must receive, and $M$ is the maximum number of candies each friend can receive.

Output

Print the number of ways Yunje can distribute the candy to the phone friends while satisfying the conditions. There may be too many ways, so print the number of ways modulo $10^9+7$ .

Examples2

Example 1
Input
```
2 0 4 4
```
Expected output
```
5
```
Example 2
Input
```
2 1 4 4
```
Expected output
```
3
```