CF712D 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

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.