Problem J. Jumps of grasshopper ≡

 Author: A. Baranov Time limit: 1 sec Input file: Standard input Memory limit: 256 Mb Output file: Standard output

Statement

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 format

Input data contains four integer numbers A, B, N и L.

Output format

Output data must contain obtained number.

Constraints

0 ≤ (B − A) ≤ 20, 1 ≤ N ≤ 40, (B − A) ≤ L ≤ 60

Sample tests

No. Standard input Standard output
1
0 10 20 40
35498634
2
1 1 2 2
3

0.135s 0.018s 15