A97501.「TAOI-1」拼凑的断音

你的面前有 $n$ 个音符，它们的动听程度由数列 $\{a_n\}$ 描述。

现在有 $n$ 种魔法，第 $i$ 种魔法会让 $a_i$ 增加 $s(s \gt 0)$。每种魔法的成功几率都为 $\dfrac{p}{q}$，并且彼此独立。

求在施加魔法情况下，最终最动听的音符的动听程度（即，$\max\limits_{i=1}^n a_i$）的期望。

第一行为四个整数 $n, p, q, s$。

第二行为 $n$ 个整数 $a_i$，由空格隔开。

请在第一行输出 1。

接着，在第二行输出所求的期望，结果保留四位小数。

数据范围

本题采用捆绑测试。

• Subtask 1（20 points）：$n \leq 15$。
• Subtask 2（15 points）：保证 $\forall i \in [1, n), a_i \leq a_{i+1}$，$a_n \geq a_{n-1}+s$。
• Subtask 3（15 points）：保证 $\forall i,j\in[1,n], a_i = a_j$。
• Subtask 4（50 points）：无特殊限制。

对于所有测试数据，$1 \leq n \leq 10^5$，$1 \leq p \lt q \leq 10^7$，$1 \leq a_i,s \leq 10^7$。

样例解释

注意到两个样例的输入相同，区别仅在于输出格式不同。

以下列举了所有可能的魔法施加情况和其对应的最大值以及出现概率：

魔法情况	动听度最大值	出现概率	对期望的贡献
${\color{black}1},{\color{black}2},{\color{black}3}$	$3$	$\dfrac{8}{27}$	$\dfrac{8}{9}$
${\color{red}3},{\color{black}2},{\color{black}3}$	$3$	$\dfrac{4}{27}$	$\dfrac{4}{9}$
${\color{black}1},{\color{red}4},{\color{black}3}$	$4$	$\dfrac{4}{27}$	$\dfrac{16}{27}$
${\color{black}1},{\color{black}2},{\color{red}5}$	$5$	$\dfrac{4}{27}$	$\dfrac{20}{27}$
${\color{red}3},{\color{red}4},{\color{black}3}$	$4$	$\dfrac{2}{27}$	$\dfrac{8}{27}$
${\color{red}3},{\color{black}2},{\color{red}5}$	$5$	$\dfrac{2}{27}$	$\dfrac{10}{27}$
${\color{black}1},{\color{red}4},{\color{red}5}$	$5$	$\dfrac{2}{27}$	$\dfrac{10}{27}$
${\color{red}3},{\color{red}4},{\color{red}5}$	$5$	$\dfrac{1}{27}$	$\dfrac{5}{27}$

可得，最终的答案为 $\dfrac{35}{9}$。

它的值约为 $3.888889$。