题目背景

flick tap flick tap 面を滑って
swipe tap swipe tap 「A.R→T」
flick tap flick tap 開いて叩いて
swipe swipe swipe swipe …もう嫌だな
ズルズル 糸が呟く

题目描述

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

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

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

本题目有 Special Judge，你可以用两种不同的方式输出答案，具体见【输出格式】处。

输入格式

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

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

输出格式

本题有两种不同的输出格式。

• 第一种输出格式：

  请在第一行输出 1。

  接着，在第二行输出所求的期望，它应当是一个实数。

  如果您的答案与标准答案相差不超过 $10^{-4}$，则判定为正确。但由于众所周知的浮点数的误差，不保证评测结果百分百准确。如果您确信自己的程序正确但无法 AC，可以尝试使用第二种输出方式。

• 第二种输出格式：

  请在第一行输出 2。

  接下来，若你求出的期望是 $\dfrac{m}{n}$（显然期望为一个有理数），则请在第二行输出它对 $998244353$ 取模的结果，即一个 $[0, 998244353)$ 的整数 $x$，使得 $xn \equiv m \pmod {998244353}$。

3 1 3 2
1 2 3

1
3.888889

3 1 3 2
1 2 3

2
554580200

提示

数据范围

本题采用捆绑测试。

• 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$。

样例解释

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

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

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

• 若使用第一种输出方式，它的值约为 $3.888889$。
• 若使用第二种输出方式，可以发现 $554580200 \times 9 \equiv 35 \pmod {998244353}$。