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.086s 0.018s 13