2014: CF712 - D. Memory and Scores
[Creator : ]
Description
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.
Input
The first and only line of input contains the four integers $a,b,k,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.
Output
Print the number of possible games satisfying the conditions modulo $10^9+7$ in one line.
Sample 1 Input
1 2 2 1
Sample 1 Output
6
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.
Sample 2 Input
1 1 1 2
Sample 2 Output
31
Sample 3 Input
2 12 3 1
Sample 3 Output
0