C. Викторина
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Манао принимает участие в викторине. Викторина состоит из n последовательных вопросов. За правильный ответ на вопрос игрок набирает 1 очко. Также в игре есть счетчик последовательных правильных ответов. Когда игрок правильно отвечает на вопрос, к числу на счетчике прибавляется 1. Если игрок неправильно отвечает на вопрос, то счетчик сбрасывается, то есть число на нем превращается в 0. Если после ответа на вопрос счетчик достигает числа k, то он сбрасывается, а счет игрока увеличивается вдвое. Заметим, что в таком случае сначала 1 очко прибавляется к счету игрока, а после происходит его удвоение. В начале игры и счет игрока, и число на счетчике последовательных ответов равны нулю.

Манао помнит, что правильно ответил ровно на m вопросов, но не помнит в каком порядке были расположены вопросы. Он пытается вычислить, каков может быть его минимальный счет. Помогите ему и выведите остаток соответствующего числа при делении на 1000000009 (109 + 9).

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

В единственной строке записаны через пробел три целых числа n, m и k (2 ≤ k ≤ n ≤ 109; 0 ≤ m ≤ n).

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

Выведите единственное число — остаток от деления минимального возможного счета Манао в викторине на 1000000009 (109 + 9).

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

Пример 1. Манао ответил на 3 вопроса из 5, и за каждые два последовательных правильных ответа его счет удваивался. Если бы Манао ответил на первый, третий и пятый вопросы, то он в сумме набрал бы 3 очка.

Пример 2. Теперь Манао ответил уже на 4 вопроса. Минимальный счет достигается в случае, если его единственный неправильный ответ был на четвертый вопрос.

Заметим, что вас просят минимизировать счет, а не остаток от деления счета на 1000000009. Например, если во время игры Манао мог набрать или 2000000000, или 2000000020 очков, ответом задачи будет 2000000000 mod 1000000009, даже хотя 2000000020 mod 1000000009 представляет собой меньшее число.