← 返回题目列表

AtCoder · summerfes2018_i

I. 粗心的尼姆

中文机器翻译题面 查看原题

配点 : 200 点

問題文

MMNMM和鸭嘴兽决定和尼姆一起去尼姆亚摊位玩。
尼姆是一种使用多堆石子进行的游戏,玩家分为先玩的玩家和后玩的玩家。
玩家可以在自己的回合中执行以下操作。

  • 选择其中一堆石头并从该堆中移走一些石头。

棋子用完且无法再拿走任何棋子的玩家就输了。

鸭嘴兽足够聪明,总是能做出最好的举动。
然而,由于 MMNMM 粗心,概率 1 - p/q 做出最佳举动,概率 p/q 是最糟糕的举动。 (每个回合的选择将独立确定。)
他们都知道这个事实。
在这里,最好的棋步是您下棋时获胜概率最高的棋步,最差的棋步是您下棋时获胜概率最低的棋步。

MMNMM 是先行者。
MMNMM 能够击败鸭嘴兽的概率是一个不可约分数。 P/Q 。
此时, 0 以上 10^9+7 的整数 M 找出可被 MQ 和 按字典顺序比较 P 分别 定义 10^9 + 7 的余数相等(即p = 10^9 + 7 在 Q 可以得到第 \mathbb{Z}/p\mathbb{Z} 中的逆元素 对于 Q^{-1} 以同样的方式定义 PQ^{-1})存在。 查找
M 。

制約

所有测试用例都满足以下约束。

  • 1 \leq N \leq 10^5
  • 1 \leq a_i \leq 10^{12}
  • 0 \leq p \leq q \leq 10^9
  • 1 \leq q
  • p 和 按字典顺序比较 q 不相交

入力

输入是按以下格式从标准输入给出的。

N p q
a_1 a_2 ... a_N
  • 第一行包含一个整数 写入 N , p , q 按此顺序写入,并用空格分隔。这是因为尼姆山 N 有很多,MMNMM做得最差。 它代表击中的概率为 p/q 。
  • 第二行包含一个整数 a_i (1 \leq i \leq N) 按此顺序写入,并用空格分隔。这是 i 尼姆山的起点 这表明有 a_i 石头。

出力

标准输出显示 MMNMM 能够击败鸭嘴兽的概率。 当 P/Q 时, 在\mathbb{Z}/p\mathbb{Z} 中 在一行上输出 P \times Q^{-1} 。


入力例 1

1 1 2
3

出力例 1

500000004

如果MMNMM先生第一次没有拿到所有的石头,他就会输,所以MMNMM先生获胜的概率是 除以 1/2 。 求放置超过
1 和 按字典顺序比较 2 \times 500000004 该值应乘以 10^9+7 的余数相等,因此 请输出500000004。


入力例 2

3 1 2
1 1 1

出力例 2

1

入力例 3

4 1 10
3 2 5 4

出力例 3

0

入力例 4

10 1 100
3 14 15 9 2 6 5 35 8 9

出力例 4

135181044