| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
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 |
