题目背景

一起长大的约定 那样清晰 拉过勾的我相信 说好要一起旅行 是你如今 唯一坚持的任性 ——《蒲公英的约定》

题目描述

清和如在玩游戏。她们有 $n$ 丛 蒲公英，每丛分别有 $s_i$ 朵。这些 蒲公英 有一个神奇的性质：有一个给定的常数 $\sigma \in (0,1)$，$x$ 朵 蒲公英 会分出 $\lfloor \sigma x \rfloor$ 朵为一组，剩下 $x-\lfloor \sigma x \rfloor$ 朵继续分组，直到分出的组没有 蒲公英 即 $\lfloor \sigma x \rfloor=0$ 为止。她们称这种现象为 任性。现在她们的每丛 蒲公英 都有 任性 的现象。她们的游戏规则如下：从清开始，两人轮流进行 旅行。一次 旅行 为选择一丛 蒲公英 并吹散这一丛的第一组中的若干朵 蒲公英，至少要吹一朵，至多吹的朵数为第一组的朵数，即不能吹散除第一组外的 蒲公英。当第一组为空时，其下一组成为第一组。若这一丛只剩下一组 蒲公英，这一丛不能再被选定。每丛 蒲公英 都不能被选定时，游戏结束，当前轮到的人落败。她们想知道如果清第一次 旅行 时等概率选择其中一丛可吹散的 蒲公英 再等概率选择吹散的朵数后两人都按最优策略操作，那么清的胜率 $x \bmod 20190816170251$ 的值将会是多少。

与 vol.2 的区别是，蒲公英 在被吹散一部分后 不会 重新分组。

输入格式

第一行两个正整数 $id,n$，其中 $id$ 表示 Subtask 编号。

第二行 $n$ 个正整数，第 $i$ 个表示 $s_i$。

若 $id>3$，第三行输入两个正整数 $p,q$ 表示 $\sigma=\dfrac{p}{q}$。

输出格式

一行一个整数，表示清的胜率 $x \bmod{20190816170251}$。

4 3
1 1 1
1 6

0

6 3
1 7 3
1 3

5047704042563

提示

简述版题意：

有 $n$ 丛 蒲公英，第 $i$ 丛有 $s_i$ 朵。给定实数 $\sigma$，每丛会分为若干组，第 $j$ 组有 $t_j$ 朵，且满足 $t_j=\left\lfloor \sigma\left(s_i - \sum\limits_{k=1}^{j-1}t_k\right) \right\rfloor$，当 $t_j=0$ 时不再分组。两人轮流操作，每次操作可以选择一丛 蒲公英，并选择一个整数 $c \in t_j$，从这丛 蒲公英 中吹散 $c$ 朵，将 $t_j$ 变为 $t_j-c$，其中 $j$ 为操作之前这丛 蒲公英 中满足 $t_j \neq 0$ 的最小正整数。必须至少吹一朵，不能操作者败。求先手第一步等概率选择任意一丛可操作的 蒲公英 再等概率选择吹散的朵数后两人都采取最优策略时先手的胜率 $x \bmod{20190816170251}$ 的值。

样例解释：

对于样例 $1$，清无法操作，胜率为 $0$。

对于样例 $2$，初始局面为 $\{0;1\},\{2,1,1,1,0;2\},\{1,0;2\}$，清可以选择第 $2$ 丛并在两种操作中选择吹散 $2$ 朵变成 $\{0;1\},\{1,1,1,0;2\},\{1,0;2\}$，选择第 $3$ 丛没有可取胜的策略，且第 $1$ 丛不能选择，总胜率为 $\dfrac{\frac{1}{2}+0}{2}=\dfrac{1}{4}$。

数据范围：

本题采用捆绑测试，各个 Subtask 的分数与限制如下。

对于 $100\%$ 的数据，$1 \le n \le 3 \times 10^5,1 \le s_i \le 10^{10},1 \le p<q \le 10^9$。

本题读入量较大，可以选择使用比赛描述中的快速读入模板以加快读入速度。