← 返回题目列表

Codeforces · 908/D

D. 新年随意安排

中文机器翻译题面 查看原题

给定三个整数 k、pa 和 pb。

您将使用以下算法构造一个序列:最初,从空序列开始。每一秒,您都会执行以下操作。以概率 pa / (pa + pb),将“a”添加到序列末尾。否则(概率为 pb / (pa + pb)),将“b”添加到序列末尾。

一旦至少有 k 个子序列形成“ab”,您就停止。确定“ab”作为结果序列中的子序列的预期次数。可以证明,这可以用 P / Q 表示,其中 P 和 Q 是互质整数,$$Q \neq 0 \bmod (10^9 + 7)$$。打印 $$P \cdot Q^{-1} \bmod (10^9 + 7)$$ 的值。

输入

第一行将包含三个整数 k、pa、pb (1 ≤ k ≤ 1 000, 1 ≤ pa, pb ≤ 1 000 000)。

输出

打印一个整数,即问题的答案。

示例

输入 #1

1 1 1

输出 #1

2

输入 #2

3 1 4

输出 #2

370000006

注意

第一个样本,我们将继续附加到我们的序列中,直到我们至少获得一次子序列“ab”。例如,我们以 1/4 的概率得到序列“ab”,以 1/16 的概率得到“bbab”,以 1/8 的概率得到“aab”。请注意,我们不可能以像“aabab”这样的序列结束,因为一旦我们有了前缀“aab”,我们就会停止我们的算法。

'ab' 在所有有效序列中出现的预期次数为 2。

对于第二个样本,答案等于 $${ \frac { 3 4 1 } { 1 0 0 } }$$。