Tung Đồng Xu Chờ Mặt Ngửa
Points
15
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
dp
Đề 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
Community Discussion