A10477. Memory and Scores

Memory and his friend Lexa are competing to get higher score in one popular computer game. Memory starts with score $a$ and Lexa starts with score $b$ . In a single turn, both Memory and Lexa get some integer in the range $[-k;k]$ (i.e. one integer among $-k,-k+1,-k+2,...,-2,-1,0,1,2,...,k-1,k$ ) and add them to their current scores. The game has exactly $t$ turns. Memory and Lexa, however, are not good at this game, so they both always get a random integer at their turn.

Memory wonders how many possible games exist such that he ends with a strictly higher score than Lexa. Two games are considered to be different if in at least one turn at least one player gets different score. There are $(2k+1)^{2t}$ games in total. Since the answer can be very large, you should print it modulo $10^{9}+7$ . Please solve this problem for Memory.

The first and only line of input contains the four integers $a$ , $b$ , $k$ , and $t$ ( $1<=a,b<=100$ , $1<=k<=1000$ , $1<=t<=100$ ) — the amount Memory and Lexa start with, the number $k$ , and the number of turns respectively.

Print the number of possible games satisfying the conditions modulo $1000000007$ ( $10^{9}+7$ ) in one line.

In the first sample test, Memory starts with $1$ and Lexa starts with $2$ . If Lexa picks $-2$ , Memory can pick $0$ , $1$ , or $2$ to win. If Lexa picks $-1$ , Memory can pick $1$ or $2$ to win. If Lexa picks $0$ , Memory can pick $2$ to win. If Lexa picks $1$ or $2$ , Memory cannot win. Thus, there are $3+2+1=6$ possible games in which Memory wins.