P6595 [YsOI2020] Plan

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.

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$**.

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$.

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$.

### Sample Explanation #### Sample Explanation $1$: One possible situation before taking modulo is: ```cpp 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: ```cpp 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: ```cpp 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