Sinh Nhật Trùng Nhau
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề bài
Một hành tinh xa xôi có một năm gồm $D$ ngày. Có $N$ người dân trên hành tinh đó, mỗi người có ngày sinh nhật được chọn ngẫu nhiên đều và độc lập từ $1$ đến $D$.
Hãy tính xác suất để không có 3 người nào có cùng ngày sinh nhật (tức là mỗi ngày trong năm có tối đa $2$ người sinh vào ngày đó), theo modulo $10^9 + 7$.
Dữ liệu vào
- Một dòng duy nhất chứa hai số nguyên $N, D$ ($1 \le N \le 2000$, $1 \le D \le 10^9$).
Dữ liệu ra
- In ra một số nguyên duy nhất là xác suất cần tìm theo modulo $10^9 + 7$.
Ví dụ
Input
3 2
Output
750000006
Giải thích
Có $2^3 = 8$ cách chọn ngày sinh cho 3 người trong năm có 2 ngày. Có $2$ cách cả 3 người trùng ngày sinh, nên có $6$ cách hợp lệ. Xác suất là $\frac{6}{8} = \frac{3}{4} \equiv 750000006 \pmod{10^9+7}$.
Giới hạn
- $1 \le N \le 2000$
- $1 \le D \le 10^9$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion