Sinh Nhật Trùng Nhau

Buổi 51 — Probability DP Dynamic Programming
Points
35
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Submissions

Đề 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
Draft saved