题目描述

现在进行一款回合制游戏。游戏分为A和B两方。

定义他们的战斗方法如下：

A和B具有完全相同的武器库，武器库中每个武器以$p_i$的概率造成1点伤害。每次攻击都会随机从武器库中进行抽取，之后攻击对方。

这本来是很公平的。但是，A和B具有不同的速度属性。这导致他们在相同的时间内能够造成的攻击次数实际上是不一样的！

假定A出手了$x$次，B出手了$y$次。现在要求计算在最终结果上B造成的伤害严格比A多的概率。答案对$10,000,019$取模。

本题数据规模较大，建议采用较为快速的读入方法。

输入格式

第一行三个整数$n, x, y$，表示共有$n$个武器，A出手$x$次，B出手$y$次。

下一行n个整数$p_i$，表示每个武器造成伤害的概率。（其中$p_i$已对$10,000,019$取模）

输出格式

一行一个整数，表示答案对$10,000,019$取模后的结果。

1 1 1
5000010

2500005

4 5 6
114 514 1919 810

2937300

样例解释

样例解释 1

这个例子中仅有1个武器，且两个人仅进行一个回合。武器的伤害概率为1/2，模下表示为5000010。

可以发现只有A造成0点伤害B造成1点伤害这种情况符合要求，概率为1/4，模下表示为2500005。

数据规模与约定

共10个测试点，每个测试点10分。 对于全体数据，均满足$1\le n, x, y \le 5 * 10^6, 0 \le p_i < 10,000,019$

在满足上述要求的基础上，一部分测试点满足下述条件：

大样例

大样例下载