D. Мемори и игра
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мемори и ее друг Лекс соревнуются, кто наберёт большее количество баллов в одной популярной игре. Изначально у Мемори a очков, а у Лекса b очков. За один ход и Мемори, и Лекс получают какое-то количество очков в диапазоне [ - k;k] (то есть одно целое число из множества  - k,  - k + 1,  - k + 2, ...,  - 2,  - 1, 0, 1, 2, ..., k - 1, k) и прибавляют его к своему текущему счёту. Игра состоит ровно из t раундов. Однако, Мемори и Лекс играют довольно плохо, поэтому каждый из них просто получает в каждом из раундов случайное число.

Мемори хочет знать количество различных сценариев игры, в которых у неё в конце будет строго больше очков, чем у Лекса. Два сценария игры считаются различными, если существует раунд, в котором хотя бы один из двух игроков получил разное количество очков. Таким образом, всего существует (2k + 1)2t различных сценариев игры. Поскольку ответ может быть очень большим, выведите остаток от его деления на 109 + 7.

Входные данные

В первой и единственной строке входных данных записаны четыре целых числа a, b, k и t (1 ≤ a, b ≤ 100, 1 ≤ k ≤ 1000, 1 ≤ t ≤ 100) — количество очков и Мемори, и Лекса в начале игры, а также число k и количество раундов соответственно.

Выходные данные

Выведите количество сценариев игры, интересных Мемори по модулю 1 000 000 007 (109 + 7).

Примеры
Входные данные
1 2 2 1
Выходные данные
6
Входные данные
1 1 1 2
Выходные данные
31
Входные данные
2 12 3 1
Выходные данные
0
Примечание

В первом примере Мемори начинает с 1, а Лекс с 2. Если Лекс получит  - 2 очка, то Мемори может получить 0, 1 или 2, чтобы победить. Если Лекс получит  - 1 очков, то Мемори для победы нужно 1 или 2. Если Лекс получит 0, то Мемори подойдёт только 2. Если же Лекс получит 1 или 2 очка, то Мемори уже не сможет победить. Таким образом, существует 3 + 2 + 1 = 6 возможных сценариев игры, в которых Мемори побеждает.