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 10^{9} 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 

