ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

NEERC 2014, Четвертьфинал Восточного подрегиона

Описание     Задачи     Отправить на проверку     Состояние проверки     Результаты
Соревнование завершено

G. Дебютный альбом

Ограничение времени: 2.0 секунды
Ограничение памяти: 64 МБ
Поп-группа «Розовый слон» приступила к записи своего дебютного альбома. Правда, у группы пока всего две песни: «Моя любовь» и «Я скучаю по тебе», но зато на каждую сделано огромное количество ремиксов.
Продюсер группы сказал, что в альбом должно войти ровно n треков, каждый из которых — это ремикс на одну из двух песен группы. Поразмыслив, музыканты решили, что диск будет интересно слушать только в том случае, если на нём не более a треков подряд будут ремиксами на песню «Моя любовь» и не более b треков подряд будут ремиксами на песню «Я скучаю по тебе». Иначе есть риск, что даже самые преданные фанаты не дослушают альбом до конца.
Сколько существует различных вариантов записи альбома из n композиций, который будет интересно слушать? Вариант записи — это последовательность чисел 1 и 2, где единицы обозначают ремиксы на песню «Моя любовь», а двойки — ремиксы на песню «Я скучаю по тебе». Два варианта считаются различными, если для некоторого i в одном варианте на i-м месте стоит единица, а в другом — двойка.

Исходные данные

В единственной строке записаны целые числа n, a, b (1 ≤ a, b ≤ 300; max(a,b) + 1 ≤ n ≤ 50 000).

Результат

Выведите количество различных вариантов записи альбома, взятое по модулю 109+7.

Пример

исходные данныерезультат
3 2 1
4

Замечания

В примере существуют следующие варианты записи: 112, 121, 211, 212.
Автор задачи: Ольга Соболева (подготовка — Алексей Самсонов)
Источник задачи: NEERC 2014, Четвертьфинал Восточного подрегиона
Чтобы отправить решение этой задачи на проверку перейдите в Архив задач: 2018. Дебютный альбом