Một người chơi những trò chơi di động đỉnh cao một hôm rất tức giận với trò chơi mà mình phải chơi trong lúc cố ký một hợp đồng. Trò chơi diễn ra như sau:
- Có một bộ bài gồm các số từ $1$ đến $2N+K$.
- Trò chơi lần lượt rút $N$ lá bài từ bộ này (không hoàn lại, nghĩa là một số không thể được rút hai lần).
- Sau những lá bài đã rút, người chơi đoán xem lá bài tiếp theo sẽ có số lớn hơn hay nhỏ hơn.
Điều khiến người chơi tức giận là do vận rủi, sau một số nhỏ luôn là một số nhỏ hơn, và sau một số lớn luôn là một số lớn hơn. Vì vậy, người chơi muốn ngăn điều này bằng cách sửa cơ chế ngẫu nhiên của trò chơi. Thay đổi này bổ sung hai quy tắc sau cho việc rút bài:
- Nếu rút một lá bài mang số từ $1$ đến $N$, số trên lá bài tiếp theo phải lớn hơn hẳn $N$ ($>N$).
- Nếu rút một lá bài mang số từ $N+K+1$ đến $2N+K$, số trên lá bài tiếp theo phải nhỏ hơn hẳn $N+K+1$ ($<N+K+1$).
Người chơi tự hỏi mình đã làm thay đổi trò chơi đến mức nào sau những chỉnh sửa này. Thước đo là tỷ lệ giữa số tất cả các dãy rút bài khác nhau có thể có trong phiên bản đã sửa với số tất cả các dãy rút bài có thể có trong phiên bản thông thường. Người chơi yêu cầu bạn tính tỷ lệ này theo modulo $10^9+7$.
Chi tiết cài đặt
Bạn cần cài đặt hàm sau:
int oyun(int N, int K)- $N$ và $K$ là các số nguyên xác định bộ bài và số lá bài cần rút như đã nêu trong đề.
- Hàm này phải trả về tỷ lệ được yêu cầu.
- Hàm này được gọi đúng một lần trong mỗi lần kiểm thử.
Giới hạn
- $1\le N\le 10^6$
- $1\le K\le 100$
Nhiệm vụ con
| Nhiệm vụ con | Điểm | Giới hạn bổ sung | Phụ thuộc |
|---|---|---|---|
| 1 | 10 | $1\le N,K\le 6$ | — |
| 2 | 18 | $1\le N\le 100$ | 1 |
| 3 | 6 | $1\le N\le 1000$ | 1, 2 |
| 4 | 47 | $1\le N\le 10^4$ | 1, 2, 3 |
| 5 | 19 | Không có giới hạn bổ sung | 1, 2, 3, 4 |
Ví dụ
oyun(2, 1)
Lời gọi hàm trên phải trả về $600000005$.
Các số của chúng ta là $1,2,3,4,5$. Ta sẽ rút 2 lá bài. Trong trường hợp thông thường, có 20 cách rút bài khác nhau. Trong trò chơi đã sửa, nếu lá đầu tiên là $1$, $2$, $4$ hoặc $5$, có 3 khả năng khác nhau cho lá thứ hai; nếu là $3$, có 4 khả năng khác nhau cho lá thứ hai. Vì vậy trò chơi đã sửa có tổng cộng 16 khả năng. $\frac{16}{20}=\frac45$. Xác suất này tương đương $600000005$ theo modulo đang dùng.
Trình chấm mẫu
Trình chấm mẫu đọc mỗi trường hợp theo định dạng sau:
$$N\ K$$
Nếu hàm được yêu cầu trả về thành công một số nguyên, trình chấm sẽ in kết quả $R$ này theo định dạng sau:
$$R$$