New Year and Arbitrary Arrangement
题号：NC234871
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定三个整数 k,p_a ,p_b 以及一个空的序列。

每一次填充操作，会有 的概率在序列末尾添加字符 'a'（不含引号），反之，有  的概率在序列末尾添加字符 'b' （不含引号）。填充操作会一直执行直到序列中出现至少 k 个形如 "ab" 的子序列。

求填充操作结束时形如 "ab" 的子序列的期望出现次数，并对  取模。

输入描述:

第一行包含三个整数 。

输出描述:

输出一个整数，代表取模后的期望次数。
示例1

输入

复制 
1 1 1

输出

复制 
2

说明

第一个样例中，我们会不断添加字符知道子序列 "ab" 至少出现了一次。例如，我们有 1/4 的概率得到序列 "ab"，有 1/16 的概率得到序列 "bbab"，以及由 1/8 的概率得到序列 "aab"。注意，我们不可能得到序列 "aabab" ，因为当我们得到前缀 "aab" 时就会立即停止操作。

所有合法序列中，子序列 "ab" 的期望出现次数是 2。
示例2

输入

复制 
3 1 4

输出

复制 
370000006

说明

第二个样例中，未取模的答案是 \frac{341}{100}。