Đố vui

Manao tham gia một bài kiểm tra gồm $n$ câu hỏi được sắp thứ tự. Mỗi câu trả lời đúng cộng cho điểm số một điểm. Trò chơi còn có một bộ đếm số câu trả lời đúng liên tiếp: khi trả lời đúng, bộ đếm tăng thêm $1$; khi trả lời sai, bộ đếm được đặt lại về $0$. Nếu sau một câu trả lời, bộ đếm chạm đến giá trị $k$ thì bộ đếm được đặt lại về $0$ và điểm số hiện tại của người chơi được nhân đôi. Lưu ý: khi câu đúng đó đưa bộ đếm lên $k$, ta cộng $1$ điểm trước, rồi mới nhân đôi tổng điểm.

Ban đầu điểm số và bộ đếm đều bằng $0$.

Manao nhớ mình đã trả lời đúng đúng $m$ câu trong tổng số $n$ câu, nhưng không nhớ thứ tự. Hãy tính điểm số nhỏ nhất có thể mà Manao đạt được, rồi in ra phần dư của giá trị đó khi chia cho ${10}^9+9$.

Lưu ý rằng đề bài yêu cầu tối thiểu hoá điểm thật (một số nguyên có thể rất lớn), rồi mới lấy phần dư — không phải tối thiểu hoá phần dư.

Dữ liệu vào

Một dòng chứa ba số nguyên $n$, $m$, $k$.

Dữ liệu ra

Một số nguyên duy nhất: phần dư của điểm số nhỏ nhất khi chia cho ${10}^9+9$.

Ràng buộc

• $2\le k\le n\le {10}^9$
• $0\le m\le n$

Ví dụ