Expected Weight with Exactly k Ones Segments

Given an integer sequence $a_1,a_2,\dots,a_n$ and a sequence of rational numbers $p_1,p_2,\dots,p_n$, consider performing independent coin flips at each position $i$ so that $c_i\in\{0,1\}$ with $P(c_i=1)=p_i$ and $P(c_i=0)=1-p_i$. The resulting binary sequence can be partitioned into maximal contiguous segments (i.e. segments that cannot be extended on either side).

Define the weight of a sequence as follows: if the number of maximal contiguous segments consisting entirely of $1$’s is exactly $k$, then its weight is (\sum_{i=1}^n c_i,a_i); otherwise, the weight is $0$.

Compute the expected weight of the sequence modulo $998244353$.

inputFormat

The input begins with a line containing two integers n and k --- the length of the sequences and the required number of contiguous 1 segments, respectively.

The second line contains n integers: a1, a2, ..., an.

The third line contains n rational numbers: p1, p2, ..., pn. Each rational number is given in the form x/y (with no spaces) representing the fraction \(\frac{x}{y}\).

outputFormat

Output a single integer --- the expected weight modulo 998244353.

Note: For any rational number, interpret the fraction with modular inverse under the modulo.

sample

3 1
1 2 3
1/1 0/1 1/2

499122177