Вступление
В жизни каждого программиста наступает день, когда последний контест проигран, и приходит время уходить на пенсию. Даже Три Программиста в своё время не избежали этой участи. А чтобы сохранить добрую память о себе, Программисты время от времени составляли задачи и проводили контесты. За это, конечно, не платили, но для настоящих программистов слава важнее денег.
Однако придумать хорошую задачу только половина дела. Нужно ещё сочинить для неё политкорректный текст.
Задача
Вся проблема в том, что текст к одной из задач очередного контеста написал Третий Программист, который вообще не знает, что такое политкорректность. Он просто сочинил историю о разведении цитрусовых в домашних условиях. В результате слово «лимон» было использовано целых N раз.
И это притом, что перед контестом задачу будет перечитывать известный цензор Александр К.! Которому лимоны напоминают об апельсинах, а он их терпеть не может. Сей факт очень беспокоит Первого и Второго Программистов они прекрасно знают, что если слово «лимон» встретится Александру более K раз подряд, то задача не будет допущена к контесту.
Поэтому Первый и Второй Программисты тайно сговорились в ночь накануне контеста залезть на сервер и заменить некоторые «лимоны» на гораздо более политкорректные «бананы» таким образом, чтобы задача всё-таки была допущена к контесту. Сколькими способами это можно сделать?
Исходные данные
Единственная строка содержит целые числа N (1 ≤ N ≤ 10000) и K (0 ≤ K ≤ N).
Результат
Вывести искомое количество способов.
Пример
исходные данные | результат |
---|
5 2 | 24 |
Замечания
Обозначим слово «лимон» буквой «Л», а слово «банан» буквой «Б». Тогда в примере исходная последовательность слов «ЛЛЛЛЛ» может быть преобразована в следующие политкорректные последовательности: «ЛЛБЛЛ», «ЛЛБЛБ», «ЛЛББЛ», «ЛЛБББ», «ЛБЛЛБ», «ЛБЛБЛ», «ЛБЛББ», «ЛББЛЛ», «ЛББЛБ», «ЛБББЛ», «ЛББББ», «БЛЛБЛ», «БЛЛББ», «БЛБЛЛ», «БЛБЛБ», «БЛББЛ», «БЛБББ», «ББЛЛБ», «ББЛБЛ», «ББЛББ», «БББЛЛ», «БББЛБ», «ББББЛ» и «БББББ».
Автор задачи: Никита Рыбак, Илья Гребнов, Дмитрий Ковалёв
Источник задачи: Timus Top Coders: Third Challenge