Background

I believe everyone already knows the following facts:

• Ysuperman is very rich.

• Ysuperman has always been good at making plans.

• Ysuperman runs a kindergarten.

• Ysuperman has collected some snacks.

• Every day, they may suddenly feel like eating their snacks in a planned way.

Problem Description

Ysuperman currently has $n$ snacks. For each snack, every day there is a probability $P$ that they will make a plan for this snack. After $T$ days from the time they make a plan, they will eat this snack. A special note: if a plan has already been made for this snack before Ysuperman makes a new plan, then in practice the snack will be eaten according to the time of the first plan.

Unfortunately, greedy kids in the kindergarten may ruin this plan. There are $m$ kids in the kindergarten, and they are eyeing Ysuperman’s snacks. For each snack, every day there is a probability $p_i$ that it will be stolen and eaten by kid $i$. If the snack has been eaten before some kid steals it, then correspondingly, that kid cannot steal it. If a snack is stolen before its plan is completed, then the related plan cannot be carried out.

Now Ysuperman wants to do a risk assessment of their plan. They offered a bounty of $114514pts$, and after multiple layers of subcontracting, the project has ended up in your hands. The values of these probabilities modulo have already been computed. After negotiation, if you solve this problem, you can get $100pts$. You need to tell them the expected number of snacks Ysuperman can eat, and the expected number of days after which all of Ysuperman’s snacks are finished (eaten up).

If a snack is eaten by a kid, then that snack no longer belongs to Ysuperman.

Note that each day, Ysuperman makes plans before the kids attempt to steal the snacks.

Ysuperman thinks floating-point precision errors are too large, so you only need to output the answers modulo $998244353$.

Input Format

The first line contains three positive integers $n,m,T$, with meanings as described in the statement.

The second line contains one positive integer $P$, representing the value of $P$ modulo $998244353$.

The third line contains $m$ positive integers $p_1,p_2,\cdots,p_m$, each representing the value of $p_i$ modulo $998244353$.

Output Format

One line with two non-negative integers, representing the expected number of snacks Ysuperman can eat, and the expected number of days after which Ysuperman’s snacks are finished. Output the answers modulo $998244353$.

5 8 11
13482572 
299473306 598946612 898419918 199648871 499122177 798595483 99824436 1

0 1

3 5 0
1
1 1 1 1 1

3 1

2 2 0
499122177
499122177 499122177

855638018 507044752

11 4 514
1919810
1919810 1919810 1919810 1919810

550831570 75142974

100000 20 227
2020
2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019

808786679 861511854

Hint

Sample Explanation

Sample Explanation $1$:

One possible situation before taking modulo is:

5 8 11  
0.1  
0.1 0.2 0.3 0.4 0.5 0.6 0.7 1

In this case, the kids will steal and eat all snacks on the first day.

Sample Explanation $2$:

One possible situation before taking modulo is:

3 5 0  
1  
1 1 1 1 1

In this case, Ysuperman will make plans and finish eating all snacks on the first day.

Sample Explanation $3$:

One possible situation before taking modulo is:

2 2 0  
0.5  
0.5 0.5

In this case, the answers are $\dfrac{8}{7}$ and $\dfrac{80}{63}$.

Since the solution process is rather complicated, please let smart readers think it through by themselves.

Constraints

If you only answer either one of the two questions correctly for a test point, you can get $25\%$ of the score for that test point.

Below is a partial scoring table as a tribute to $\text{NOI}$: | Test Point ID | $n$ | $m$ | $T$ | $P$ | Special Property | | :-----------: | -----------: | -----------: | -----------: | -----------: | :-----------: | | 1 | $=1$ | $=1$ | $=0$ | No other constraints | None | | 2 | $=1$ | $=10$ | $=1$ | $=1$ | $1$ | | 3 | $=1$ | $\le100$ | $=227$ | $=1$ | $2$ | | 4 | $\le 20$ | $\le 1000$ | $=4$ | No other constraints | None | | 5 | $\le 100$ | $\le 1000$ | $=4$ | No other constraints | None | | 6 | $\le 1000$ | $\le 1000$ | $=227$ | $=0$ | $1$ | | 7 | $\le 100000$ | $\le 100000$ | $=233$ | $=1$ | $2$ | | 8 | $\le1919820$ | $=114514$ | $=2333$ | $=0$ | $2$ | | 9 | $\le1919820$ | $=114514$ | $=2333$ | $=0$ | $2$ | | 10 | $=100000$ | $=100000$ | $=3$ | No other constraints | $2$ | | 11 | $=114514$ | $=114514$ | $=3$ | No other constraints | None | | 12 | $\le1919820$ | $=114514$ | $=0$ | No other constraints | $2$ | | 13 | $\le 1919820$ | $=1$ | $\le 227$ | No other constraints | None | | 14 | $\le 1919820$ | $\le114514$ | $\le 227$ | No other constraints | $2$ | | 15 | $\le 1919820$ | $=1$ | $\le 500$ | $=1$ | None | | 16 | $\le 1919820$ | $\le 114514$ | $\le 500$ | $=1$ | None | | 17 | $\le 1919820$ | $\le 114514$ | $\le 500$ | $=1$ | None | | 18 | $\le 1919820$ | $\le 114514$ | $=0$ | No other constraints | None | | 19 | $\le 1919820$ | $\le 114514$ | $=0$ | No other constraints | None | | 20 | $\le 100000$ | $\le 100000$ | $\le 500$ | No other constraints | $2$ | | 21 | $\le 100000$ | $\le 100000$ | $\le 500$ | No other constraints | None | | 22 | $\le 100000$ | $\le 100000$ | $\le 500$ | No other constraints | None | | 23 | $\le 1919820$ | $\le 114514$ | $\le 2333$ | No other constraints | None | | 24 | $\le 1919820$ | $\le 114514$ | $\le 2333$ | No other constraints | None | | 25 | $\le 1919820$ | $\le 114514$ | $\le 2333$ | No other constraints | $2$ |

For $100\%$ of the testdata, it holds that $1\le n\le 1919820,1\le m \le 114514,0\le T \le 2333,0\le P< 998244353,1\le p_i<998244353$.

Special property $1$: There exists an $i$ such that $p_i=1$.

Special property $2$: All $p_i$ are equal.

Translated by ChatGPT 5