Поп-группа «Розовый слон» приступила к записи своего дебютного альбома.
Правда, у группы пока всего две песни: «Моя любовь» и «Я скучаю по
тебе», но зато на каждую сделано огромное количество ремиксов.
Продюсер группы сказал, что в альбом должно войти ровно 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, Четвертьфинал Восточного подрегиона