Background

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

Problem Description

There are $n$ notes in front of you, and their pleasantness is described by the sequence $\{a_n\}$.

Now there are $n$ types of magic. The $i$-th type of magic will increase $a_i$ by $s$ ($s \gt 0$). The success probability of each type of magic is $\dfrac{p}{q}$, and they are independent of each other.

Find the expected value of the pleasantness of the most pleasant note in the end (that is, $\max\limits_{i=1}^n a_i$) after applying the magic.

This problem has a Special Judge. You may output the answer in two different ways. See [Output Format] for details.

Input Format

The first line contains four integers $n, p, q, s$.

The second line contains $n$ integers $a_i$, separated by spaces.

Output Format

This problem has two different output formats.

• The first output format:

  Output 1 on the first line.

  Then, output the required expectation on the second line. It should be a real number.

  If your answer differs from the standard answer by at most $10^{-4}$, it will be judged correct. However, due to well-known floating-point errors, the judging result is not guaranteed to be 100% accurate. If you are sure your program is correct but cannot get AC, you may try the second output format.

• The second output format:

  Output 2 on the first line.

  Next, if the expectation you computed is $\dfrac{m}{n}$ (clearly the expectation is a rational number), then output on the second line its value modulo $998244353$, i.e. an integer $x$ in $[0, 998244353)$ such that $xn \equiv m \pmod {998244353}$.

3 1 3 2
1 2 3

1
3.888889

3 1 3 2
1 2 3

2
554580200

Hint

Constraints

This problem uses bundled testdata.

• Subtask 1 (20 points): $n \leq 15$.
• Subtask 2 (15 points): Guaranteed that $\forall i \in [1, n), a_i \leq a_{i+1}$, and $a_n \geq a_{n-1}+s$.
• Subtask 3 (15 points): Guaranteed that $\forall i,j\in[1,n], a_i = a_j$.
• Subtask 4 (50 points): No special constraints.

For all testdata, $1 \leq n \leq 10^5$, $1 \leq p \lt q \leq 10^7$, $1 \leq a_i,s \leq 10^7$.

Sample Explanation

Note that the two sample inputs are the same; the only difference is the output format.

Below are all possible cases of whether each magic succeeds, along with the corresponding maximum value, its probability, and its contribution to the expectation:

Therefore, the final answer is $\dfrac{35}{9}$.

• Using the first output format, its value is approximately $3.888889$.
• Using the second output format, you can find that $554580200 \times 9 \equiv 35 \pmod {998244353}$.

Translated by ChatGPT 5