#P9581. I‘m

    ID: 6197 传统题 4000ms 512MiB 尝试: 2 已通过: 2 难度: 6 上传者: 标签>CF2000提高全概率公式二项分布补事件计算一维前缀和组合数乘法递推模逆元逆元线性递推快速幂

I‘m

题目描述

鸡和猫正在对打。

世界上共有 nn 种武器,第 ii 种武器的攻击力为 pip_i。使用该武器攻击时,有 pip_i 概率造成 11 点伤害,1−pi1 − p_i 概率不造成伤害。

鸡会攻击猫 AA 次,而猫会攻击鸡 BB 次。双方每次攻击都会等概率随机一个武器攻击对方。

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

输入格式

第一行有三个正整数 n,A,Bn, A, B,第二行有 nn 个整数 pip_i(输入的 pip_i 已经取过模)。

输出格式

输出一行一个整数,表示答案对 1000001910000019 取模后的结果。

样例

4 5 6
114 514 1919 810
2937300

子任务

对于 100%100\% 的数据,1≤n,A≤5×1061\le n,A\le 5\times 10^6,1≤B≤10181\le B\le 10^{18},0≤pi<1000000190\le p_i<100000019。

  • 子任务 11(1010 分):A,B≤10A,B\le 10。
  • 子任务 22(1010 分):n,A,B≤103n,A,B\le 10^3。
  • 子任务 33(1010 分):A≤100A\le 100,依赖子任务 11。
  • 子任务 44(3030 分):B≤2×106B\le 2\times 10^6,依赖子任务 1,21,2。
  • 子任务 55(4040 分):无特殊限制,依赖子任务 3,43,4。