| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P194SUMJ - Điểm số |
Time limit: 1s
Đ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 n 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ố k , 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 n
Haley nhớ rằng cậu trả lời đúng m 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 ≤ 109;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
| Được gửi lên bởi: | adm |
| Ngày: | 2019-08-10 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
