Codeforces Round 370 (Div. 2) |
---|
Закончено |
Мемори и ее друг Лекс соревнуются, кто наберёт большее количество баллов в одной популярной игре. Изначально у Мемори 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 возможных сценариев игры, в которых Мемори побеждает.
Название |
---|