e-olymp
Məsələlər

Басня о лимоне

Басня о лимоне

В жизни каждого программиста наступает день, когда последний контест проигран, и приходит время уходить на пенсию. Даже Три Программиста в своё время не избежали этой участи. А чтобы сохранить добрую память о себе, Программисты время от времени составляли задачи и проводили контесты. За это, конечно, не платили, но для настоящих программистов слава важнее денег.

Однако придумать хорошую задачу – только половина дела. Нужно ещё сочинить для неё политкорректный текст.

Вся проблема в том, что текст к одной из задач очередного контеста написал Третий Программист, который вообще не знает, что такое политкорректность. Он просто сочинил историю о разведении цитрусовых в домашних условиях. В результате слово "лимон" было использовано целых N раз.

И это притом, что перед контестом задачу будет перечитывать известный цензор Александр К.! Которому лимоны напоминают об апельсинах, а он их терпеть не может. Сей факт очень беспокоит Первого и Второго Программистов – они прекрасно знают, что если слово "лимон" встретится Александру более K раз подряд, то задача не будет допущена к контесту.

Поэтому Первый и Второй Программисты тайно сговорились в ночь накануне контеста залезть на сервер и заменить некоторые "лимоны" на гораздо более политкорректные "бананы" таким образом, чтобы задача всё-таки была допущена к контесту. Сколькими способами это можно сделать?

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

Единственная строка содержит целые числа N (1N10000) и K (0KN).

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

Вывести искомое количество способов.

Подсказка: Обозначим слово "лимон" буквой "Л", а слово "банан" – буквой "Б". Тогда в примере исходная последовательность слов "ЛЛЛЛЛ" может быть преобразована в следующие политкорректные последовательности: "ЛЛБЛЛ", "ЛЛБЛБ", "ЛЛББЛ", "ЛЛБББ", "ЛБЛЛБ", "ЛБЛБЛ", "ЛБЛББ", "ЛББЛЛ", "ЛББЛБ", "ЛБББЛ", "ЛББББ", "БЛЛБЛ", "БЛЛББ", "БЛБЛЛ", "БЛБЛБ", "БЛББЛ", "БЛБББ", "ББЛЛБ", "ББЛБЛ", "ББЛББ", "БББЛЛ", "БББЛБ", "ББББЛ" и "БББББ".

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri
5 2
Çıxış verilənləri
24
Müəllif Н.Рыбак, И.Гребнов, Д.Ковалёв