Memory and Scores

AB两人玩一个游戏，两人玩t轮 每人每次随机且等概率从[-k,k]中取一个数字加到总得分中 得分高者赢 已知A B初始分别有a b分，问A取得胜利的概率是多少 为了避免小数精度问题答案*(2k+1)^t mod 1000000007

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.

1 2 2 1

6

1 1 1 2

31

2 12 3 1

0

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.