题目描述

鸡和猫正在对打。

世界上共有 $n$ 种武器，第 $i$ 种武器的攻击力为 $p_i$。使用该武器攻击时，有 $p_i$ 概率造成 $1$ 点伤害，$1 − p_i$ 概率不造成伤害。

鸡会攻击猫 $A$ 次，而猫会攻击鸡 $B$ 次。双方每次攻击都会等概率随机一个武器攻击对方。

猫很想赢，所以它想知道：攻击结束后，鸡受到的伤害严格大于猫受到的伤害的概率，对 $10000019$ 取模。

输入格式

第一行有三个正整数 $n, A, B$，第二行有 $n$ 个整数 $p_i$（输入的 $p_i$ 已经取过模）。

输出格式

输出一行一个整数，表示答案对 $10000019$ 取模后的结果。

样例

4 5 6
114 514 1919 810

2937300

子任务

对于 $100\%$ 的数据，$1\le n,A\le 5\times 10^6$，$1\le B\le 10^{18}$，$0\le p_i<100000019$。

• 子任务 $1$（$10$ 分）：$A,B\le 10$。
• 子任务 $2$（$10$ 分）：$n,A,B\le 10^3$。
• 子任务 $3$（$10$ 分）：$A\le 100$，依赖子任务 $1$。
• 子任务 $4$（$30$ 分）：$B\le 2\times 10^6$，依赖子任务 $1,2$。
• 子任务 $5$（$40$ 分）：无特殊限制，依赖子任务 $3,4$。