Tung Đồng Xu Chờ Mặt Ngửa

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

Đề bài

An có một đồng xu không cân đối: mỗi lần tung, xác suất ra mặt ngửa là $p = \frac{u}{v}$ và xác suất ra mặt sấp là $1 - p$.

An tung đồng xu liên tiếp cho đến khi nhận được $n$ lần mặt ngửa liên tiếp thì dừng lại. Hãy tính kỳ vọng số lần tung đồng xu của An, theo modulo $10^9 + 7$.

Dữ liệu vào

  • Một dòng duy nhất chứa ba số nguyên $n, u, v$ ($1 \le n \le 10^5$, $1 \le u \le v \le 10^9$, $v$ không chia hết cho $10^9 + 7$).

Dữ liệu ra

  • In ra một số nguyên duy nhất là kỳ vọng số lần tung theo modulo $10^9 + 7$ (nếu kết quả là phân số tối giản $\frac{P}{Q}$, in ra $P \cdot Q^{-1} \bmod (10^9 + 7)$).

Ví dụ

Input
2 1 2
Output
6

Giải thích

Với $p = \frac{1}{2}$ và $n = 2$, kỳ vọng số lần tung để được 2 mặt ngửa liên tiếp là $6$.

Giới hạn

  • $1 \le n \le 10^5$
  • $1 \le u \le v \le 10^9$
  • Thời gian: 2 giây
  • Bộ nhớ: 256 MB
Draft saved