配点 : 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