Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

C. Белое, черное и снова белое
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Поликарп уверен, что жизнь его поддается описанию: «сначала идет белая полоса, потом черная, потом снова белая». Вот и в ближайшие n дней он уверен — это правило будет выполняться. Поликарп знает, что его ожидает w хороших событий и b не очень. Каждый день будет происходить хотя бы одно событие. Так как каждый из дней однозначно характеризуется как часть белой или черной полосы, в каждый из дней будут случаться события только одного типа (либо хорошие, либо не очень).

Какое количество различных вариантов развития истории может быть в ближайшие n дней, если Поликарпа ждет сначала белая полоса (полоса из исключительно хороших событий, длина полосы не менее 1 дня), потом черная полоса (полоса из исключительно событий «не очень», длина полосы не менее 1 дня) и снова белая полоса (полоса из исключительно хороших событий, длина полосы не менее 1 дня). Каждый из n дней будет принадлежать ровно к одной из трех полос.

Учтите, что события даже одного типа различимы между собой. Даже если события происходят в один день, они происходят в некотором порядке (одновременных событий не бывает).

Напишите программу, которая выводит количество возможных конфигураций распределения событий по дням по модулю 1000000009 (109 + 9). Ознакомьтесь с примерами для уточнения того, какие способы следует различать.

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

В единственной строке входных данных записаны целые числа n, w и b (3 ≤ n ≤ 4000, 2 ≤ w ≤ 4000, 1 ≤ b ≤ 4000). Гарантируется, что w + b ≥ n.

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

Выведите искомое количество способов по модулю 1000000009 (109 + 9).

Примеры
Входные данные
3 2 1
Выходные данные
2
Входные данные
4 2 2
Выходные данные
4
Входные данные
3 2 2
Выходные данные
4
Примечание

Будем обозначать хорошие события цифрами от 1, а события «не очень» буквами от 'a'. Вертикальными чертами будем разделять дни.

В первом примере возможные варианты: «1|a|2» и «2|a|1». Во втором примере возможные варианты: «1|a|b|2», «2|a|b|1», «1|b|a|2» и «2|b|a|1». Во третьем примере возможные варианты: «1|ab|2», «2|ab|1», «1|ba|2» и «2|ba|1».