Sưu Tập Thẻ Bài
Points
22
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Bộ sưu tập thẻ bài gồm $n$ loại thẻ khác nhau. Mỗi gói thẻ chứa đúng $1$ thẻ, và loại thẻ bên trong được chọn ngẫu nhiên đều trong $n$ loại (mỗi loại có xác suất $\frac{1}{n}$).
Hiện tại Minh đã có sẵn $k$ loại thẻ khác nhau. Minh muốn mua thêm các gói thẻ cho đến khi có ít nhất $m$ loại thẻ khác nhau. Hãy tính kỳ vọng số gói thẻ Minh cần mua thêm, theo modulo $10^9 + 7$.
Dữ liệu vào
- Một dòng duy nhất chứa ba số nguyên $n, k, m$ ($1 \le n \le 10^6$, $0 \le k \le m \le n$).
Dữ liệu ra
- In ra một số nguyên duy nhất là kỳ vọng số gói thẻ cần mua thêm theo modulo $10^9 + 7$.
Ví dụ
Input
3 0 3
Output
500000009
Giải thích
Với $n = 3, k = 0, m = 3$, kỳ vọng là $\frac{3}{3} + \frac{3}{2} + \frac{3}{1} = \frac{11}{2} \equiv 500000009 \pmod{10^9+7}$.
Giới hạn
- $1 \le n \le 10^6$
- $0 \le k \le m \le n$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion