Problem Background

It is widely known that:
- Ysuperman is very wealthy.
- Ysuperman is always good at making plans.
- Ysuperman manages a kindergarten.
- Ysuperman collects some snacks.
- Each day, Ysuperman might suddenly want to plan to eat some of these snacks.

Problem Description

Ysuperman currently has $n$ snacks. For each snack, there is a probability $P$ that Ysuperman will plan to eat it. Once a plan is made, Ysuperman will eat the snack $T$ days later. It should be noted that if Ysuperman makes another plan for the same snack before the first plan is executed, the snack will still be eaten according to the timing of the first plan.

Unfortunately, the greedy kids in the kindergarten can disrupt this plan. There are $m$ kids in the kindergarten, each eyeing Ysuperman's snacks. For each snack, there is a probability $p_i$ that the $i$-th kid will steal and eat it. If the snack is eaten by Ysuperman before any kid can steal it, then the kid cannot steal it. If a snack is stolen before the plan is executed, the plan fails.

Now, Ysuperman wants to assess the risk of this plan. Ysuperman has offered a reward of $114514pts$. This project has been passed down to you, and you can earn $100pts$ if you solve the problem. You need to inform Ysuperman of how many snacks Ysuperman can expect to eat, and the expected number of days before Ysuperman's snacks are eaten.

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

Note that Ysuperman makes plans before the kids can steal the snacks.

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

Input Format

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

The second line contains a positive integer $P$, which is the result of $P$ modulo $998244353$.

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

Output Format

One line with two natural numbers. These represent the expected number of snacks Ysuperman can eat and the expected number of days before Ysuperman's snacks are eaten, both modulo $998244353$.

Sample Input and Output

Input Sample #1

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

Output Sample #1

0 1

Input Sample #2

3 5 0
1
1 1 1 1 1

Output Sample #2

3 1

Input Sample #3

2 2 0
499122177
499122177 499122177

Output Sample #3

855638018 507044752

Input Sample #4

11 4 514
1919810
1919810 1919810 1919810 1919810

Output Sample #4

550831570 75142974

Input Sample #5

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

Output Sample #5

808786679 861511854

Notes/Hints

Sample Explanation

Sample Explanation #1:

One possible scenario before modulo operation:

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

In this scenario, the kids will eat all the snacks on the first day.

Sample Explanation #2:

One possible scenario before modulo operation:

3 5 0  
1  
1 1 1 1 1

In this scenario, Ysuperman will plan and eat all the snacks on the first day.

Sample Explanation #3:

One possible scenario before modulo operation:

2 2 0  
0.5  
0.5 0.5

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

Since the solution process is complex, the reader is encouraged to think for themselves.

Data Range

If you answer either question correctly for a test case, you can earn $25\%$ of the points for that test case.

Here is the partial credit table inspired by NOI:

For $100\%$ of the data, it satisfies $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.

见题面 Input 部分

见题面 Output 部分