| Автор: | A. Baranov | Ограничение времени: | 1 сек | |
| Входной файл: | Стандартный вход | Ограничение памяти: | 256 Мб | |
| Выходной файл: | Стандартный выход |
Сверчок движется вдоль числовой прямой, совершая скачки целочисленной длины. При этом он может скакать как в положительном, так и в отрицательном направлении. Размер одного скачка не может равняться нулю.
Требуется посчитать число всех различных способов, которыми сверчок может добраться из точки A в точку B, совершив при этом не более N скачков, суммарная длина которых не превосходила бы некоторое заданное L.
Так как полученное число может оказаться слишком большим, в качестве ответа следует вывести остаток от его деления на 109.
Во входных данных записаны четыре целых числа A, B, N и L.
Выходные данные должны содержать полученное число.
0 ≤ (B − A) ≤ 20, 1 ≤ N ≤ 40, (B − A) ≤ L ≤ 60
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|
| 2 | |
|