| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P194SUMF - Nhảy cóc |
Time limit: 1s
Bạn đang chơi một trò chơi kỳ lạ, thể thức như sau:
- Có n vị trí, được đánh số từ 1 đến n. Bạn được chọn vị trí để bắt đầu chơi.
- Bạn được di chuyển k-1 lần: với mỗi lần di chuyển, nếu đang ở vị trí x, bạn sẽ được quyền đi tới vị trí y thoả mãn 1 ≤ y ≤ x+m và vị trí đó chưa từng được đến. Nói cách khác, khi kết thúc trò chơi bạn sẽ đặt chân lên đúng k vị trí khác nhau.
Hai lượt chơi được coi là khác nhau nếu tồn tại một số thứ tự i sao cho vị trí thứ i được tới (sau lượt thứ i-1) của hai lượt chơi là khác nhau.
Hãy tìm số lượt chơi khác nhau có thể có. Vì đáp số có thể rất lớn, in ra đáp số modulo 109 + 7.
Input
Dòng đầu tiên và duy nhất chứa ba số nguyên n, k, m (1 ≤ n ≤ 109, 1 ≤ k ≤ min(n, 12), 1 ≤ m ≤ 4) – lần lượt là số vị trí của trò chơi, số vị trí cần di chuyển đến, và hằng số điều kiện m.
Output
In ra một số nguyên duy nhất là kết quả bài toán, lấy modulo 109 + 7.
Example
Input
Output
3 3 1
4
4 2 1
9
5 5 4
120
100 1 2
100
| Đượ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 |
