Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

P205PROB - Điểm số

Đang chơi cờ thì Haley chợt nhớ đến bài kiểm tra toán buổi sáng. Bài kiểm tra gồm câu hỏi trắc nghiệm và được làm trên máy tính. Với mỗi câu trả lời đúng, bài kiểm tra của Haley được cộng 1 điểm. Bên cạnh phần làm bài có một bộ đếm. Khi trả lời đúng, bộ đếm này tăng thêm 1. Nếu Haley trả lời sai một câu hỏi, bộ đếm được đặt lại, nghĩa là số ở bộ đếm giảm xuống còn 0. Khi bộ đếm đạt đến số , sau đó nó được đặt lại và điểm của Haley được nhân đôi. Khi bắt đầu làm bài kiểm tra, cả điểm số của Haley và bộ đếm các câu trả lời đúng liên tiếp đều được đặt thành 0. Biết rằng Haley làm liên tục từ câu 1 đến câu

Haley nhớ rằng cậu trả lời đúng câu hỏi, nhưng cậu không nhớ thứ tự câu hỏi trả lời đúng. Haley muốn tìm số điểm thấp nhất cậu có thể có. Hãy giúp Haley nhé vì cậu ấy đang tập trung vào ván cờ.

Input

Một dòng duy nhất gồm ba số nguyên n, m, k (2 <= k <= n <= 10^9 ; 0 <= m <= n ).

Output

Gồm một số nguyên là số điểm nhỏ nhất có thể có của Haley chia lấy dư cho 10^9 + 9

Example

Input

Output

5 3 2

3

Giải thích:

Haley trả lời đúng 3 trên 5 câu hỏi, và điểm cậu ấy sẽ nhân đôi nếu trả lời đúng 2 câu hỏi liên tiếp. Để đạt số điểm tối thiểu thì Haley sẽ trả lời đúng câu 1, 3, 5 và điểm tối thiểu đạt được là 3.


Được gửi lên bởi:adm
Ngày:2020-09-13
Thời gian chạy:1s
Giới hạn mã nguồn:5000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM64 CPP CPP14 JAVA PYTHON PYTHON3

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.