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