Snack Planning and Risk Evaluation

Ysuperman has ( n ) snacks. For each snack, every day, before any other event, Ysuperman makes a plan for it with probability ( P ). Once a plan is made for a snack (and note that if a snack already had a plan before, new plans are ignored), it is scheduled to be eaten exactly ( T ) days later. However, there is a catch. There are ( m ) little kids in the kindergarten, and for each snack, on every day the ( i\text{-th} ) kid has a probability ( p_i ) to steal that snack. In each day the order of events is as follows:

1. Ysuperman makes plans for any snack that is still not planned.
2. Then, each kid may attempt to steal every snack (regardless of whether a snack has been planned or not).

If a snack is stolen on any day before (or on the same day of) its planned execution (eating) time, then the snack is lost to Ysuperman and the corresponding plan is canceled. (On the planned eating day, Ysuperman eats the snack before the kids try to steal it.)

Assume that all events on different snacks are independent. All probabilities ( P ) and ( p_i ) are given modulo ( 998244353 ) (that is, they are provided as integers which represent rational numbers modulo ( 998244353 )).

Ysuperman wants to assess the risk of his plan. Your task is to compute two values modulo ( 998244353 ):

1. The expected number of snacks that Ysuperman will eventually eat.
2. The expected day on which all of his (successfully eaten) snacks have been consumed, i.e. the expected finishing day (if no snack is eaten then output 0).

A short explanation of the dynamics for a single snack:

Let the ( m ) kids have probabilities ( p_1, p_2, \dots, p_m ) of stealing the snack each day. Define [ R = \prod_{i=1}^{m} (1-p_i) \quad \text{and} \quad q = (1-P),R. ] Then, on any day when the snack is still unplanned, the events occur in order:

• With probability ( P ), Ysuperman makes a plan. Immediately after, the snack survives the day with probability ( R ). After planning on day ( d ), it will be eaten on day ( d+T ) provided that in every day from ( d+1 ) to ( d+T-1 ) the kids do not steal it (each day surviving with probability ( R )).
• With probability ( 1-P ) the snack is not planned and it survives the day with probability ( R ) (otherwise it is stolen).

Thus one may show that the probability for a snack to eventually be eaten is [ A = \frac{P,R^{T}}{1-q} \quad \text{with} \quad q=(1-P)R, ] and the expected consumption day for that snack (if it is eaten on the first successful planning day ( d ) with consumption day ( d+T )) has a shifted geometric distribution. In particular, it can be shown that the expected finishing day among all ( n ) snacks is [ E = T\Bigl(1-(1-A)^n\Bigr)+\sum_{j=1}^{n}(-1)^{j+1}\binom{n}{j}\frac{(Aq)^j}{1-q^j}, ] where the convention is that if no snack is eaten then the finishing day is (0).

You are to compute and output these two numbers modulo ( 998244353 ).

inputFormat

The input consists of three lines:

The first line contains three integers: ( n ), ( m ) and ( T )

The second line contains a single integer: ( P ) (the probability that Ysuperman makes a plan for a snack on any given day, given modulo ( 998244353 )).

The third line contains ( m ) space‐separated integers: ( p_1, p_2, \dots, p_m ) (each is the stealing probability for one kid, modulo ( 998244353 )).

It is guaranteed that all given probabilities are provided as integers representing elements in the field modulo ( 998244353 ).

outputFormat

Output two space‐separated integers: the expected number of snacks eaten by Ysuperman and the expected finishing day (i.e. the day by which all his eaten snacks have been consumed), both taken modulo ( 998244353 ).

sample

1 1 1
499122177
332748118

EXPECTED_OUTPUT_CASE1