题目描述

还记得前几题中的 Eli 和 Deni 吗？你知道他们还养了一只小猴子吗？

这只小猴子会不停敲击键盘，它每次只会按下 0 或 1：

• 按下 0 的概率为 $p$；
• 按下 1 的概率为 $1-p$。

每按下一次后，小猴子都会查看到目前为止的按键序列；只要它还没有看到预先给定的长度为 $N$ 的二进制模式串 $S$，它就会继续按下去。一旦它看到了这个模式串，就会停止。

例如，当模式串为 1010 时，以下序列都可能作为一次结束时的完整按键序列：

• 11011001011010
• 1010
• 1111111010

已知模式串 $S$，请你求出：直到第一次看到该模式串为止，按键次数的期望值，并将答案对 $10^9+7$ 取模后输出。

输入格式

第一行输入一个整数 $N$，表示模式串长度。
第二行输入两个整数 $p_A,p_B$，满足

$$p=\frac{p_A}{p_B}$$

即小猴子按下 0 的概率为 $\dfrac{p_A}{p_B}$。
第三行输入一个长度为 $N$ 的仅由 0 和 1 组成的字符串 $S$。

输出格式

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

关于“取模后的有理数”

设期望值为 $\dfrac{P}{Q}$，其中 $Q\ne 0$。你需要输出一个整数 $a$，满足：

$$0\le a<10^9+7$$

且

$$a\cdot Q\equiv P\pmod{10^9+7}$$

也就是说，输出的是 $\dfrac{P}{Q}$ 在模 $10^9+7$ 意义下的值。

你可以使用如下事实：对于任意非零整数 $x$，在模 $10^9+7$ 下它的逆元为

$$x^{10^9+5}\bmod (10^9+7)$$

因此最终答案可以写成：

$$a\equiv P\cdot Q^{10^9+5}\pmod{10^9+7}$$

说明

若把所有可能的停止序列记为第 $i$ 种，其长度为 $x_i$，出现概率为 $p_i$，则期望定义为：

$$E[X]=\sum_i x_i\cdot p_i$$

数据范围

• $1\le N\le 10^7$
• $1\le p_A<p_B<10^9+7$

子任务

子任务	分值	$N$ 范围	额外限制
1	11	$\le 3000$	$S$ 的形式为 11111... 或 00000...
2	6		$S$ 的形式为 01111... 或 10000...
3	5		$S$ 中不存在相邻的 0
4	42	$\le 200$	无
5	11	$\le 3000$
6	10	$\le 5\times 10^5$
7	15	$\le 10^7$

只有通过某个子任务中的全部测试点，才能获得该子任务的分数。

样例 1

输入

1
1 2
0

输出

2

解释

此时 $p=\dfrac12$。小猴子会一直按键，直到第一次看到 0 为止，因此期望按键次数为 $2$。

样例 2

输入

4
3 4
1011

输出

333333425

解释

此时 $p=\dfrac34$。答案对应的真实值为

$$89.333\ldots = 89.\overline{3}=\frac{268}{3}$$

而

$$333333425\times 3 = 1000000275 \equiv 268 \pmod{10^9+7}$$

因此输出 333333425。