| Author: | A. Baranov | Time limit: | 1 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
Grasshopper moves along number line by jumps of integer length. It can jump both to positive and negative directions. Length of each jump can't equal zero.
It is required to calculate count of all different ways that grasshopper can get from point A to point B
making at most N jumps,
whose total length shouldn't exceed some given L.
Since obtained count may be very great, remainder of its division by 109 expected as answer.
Input data contains four integer numbers A, B, N и L.
Output data must contain obtained number.
0 ≤ (B − A) ≤ 20, 1 ≤ N ≤ 40, (B − A) ≤ L ≤ 60
| No. | Standard input | Standard output |
|---|---|---|
| 1 | |
|
| 2 | |
|