题目描述

小蓝在做一种随机字符串实验。她有一个长度为 $N$ 的序列，初始时所有位置均为 $0$。实验开始后，序列中的每个位置独立地以概率 $\frac{P}{Q}$ 变为 $1$，其余位置保持为 $0$。

实验结束后，所有连续的 $0$ 会被 $1$ 分隔成若干段。

设从左到右出现的非空连续零段长度依次为 $l_1, l_2, \dots, l_k$。

小蓝定义该序列的价值为

也就是说，价值是所有相邻零段长度乘积之和。若零段数量少于 $2$，则价值为 $0$。

现在，请你计算 $S$ 的期望值，并输出其对 $10^9 + 7$ 取模后的结果。

输入格式

输入一行，包含三个整数 $N, P, Q$，分别表示序列长度，以及每个位置变为 $1$ 的概率的分子和分母。

保证 $0 \le P \le Q$，$Q > 0$，且 $\gcd(P, Q) = 1$。

输出格式

输出一行，一个整数，表示 $S$ 的期望值对 $10^9 + 7$ 取模后的结果。

若期望值为分数 $\frac{a}{b}$，则输出 $a \times b^{-1} \bmod (10^9 + 7)$，其中 $b^{-1}$ 表示 $b$ 在模 $10^9 + 7$ 意义下的乘法逆元。

4 1 2

937500007

提示

【样例说明】

当 $N=4$ 且每个位置以概率 $\frac{1}{2}$ 变为 $1$ 时，所有 $2^4$ 种状态等概率出现，但只有以下状态的价值非零：

因此 $E[S] = \frac{2+2+1+1+1}{16} = \frac{7}{16}$。在模 $10^9 + 7$ 意义下，$\frac{7}{16}$ 等于 $937500007$。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le N \le 20$。

对于所有评测用例，$1 \le N \le 10^6$，$0 \le P \le Q \le 10^9$，$\gcd(P, Q) = 1$。