Description

Given an integer sequence $a_1,a_2,\dots,a_n$ of length $n$, and a rational sequence $p_1,p_2,\dots,p_n$. At each position there is a random coefficient $c_i \in \{0,1\}$, where $P(c_i = 1) = p_i$ and $P(c_i = 0) = 1 - p_i$.

Note that when writing the random coefficients as a sequence, it can be divided into several maximal consecutive segments of $0$ and $1$. “Maximal” means it cannot be extended to either side. Define the value (weight) of a coefficient sequence as follows: if the coefficient sequence has exactly $k$ maximal consecutive segments of $1$, then its value is $\sum\limits_{i=1}^n c_i a_i$; otherwise, its value is $0$.

Find the expected value of this coefficient sequence. Output the answer modulo $998244353$.

Input Format

The first line contains two positive integers $n,k$.

The second line contains $n$ non-negative integers $a_1,a_2,\dots,a_n$.

The third line contains $n$ non-negative integers $p_1,p_2,\dots,p_n$, given modulo $998244353$.

Output Format

One line with one non-negative integer, representing the expectation.

5 1
1 2 3 4 5
1 1 1 1 1

15

3 2
1 2 3
499122177 499122177 499122177

499122177

Hint

Sample Explanation

For the first sample, $c_i$ must be $1$, and there must be exactly $1$ maximal consecutive segment, so the value must be $1 + 2 + 3 + 4 + 5 = 15$.

For the second sample, the value is non-zero only when $c_1 = 1,c_2 = 0,c_3 = 1$, and the probability of this case is $\frac 12 \times \frac 12 \times \frac 12 = \frac 18$, so the expectation is $\frac{1+3}8 = \frac 12 \equiv 499122177 \pmod {998244353}$.

Constraints

For $30\%$ of the testdata, $n \le 20$.

For $60\%$ of the testdata, $n \le 10^3$.

For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le k \le \min\left(20,\left\lfloor\frac{n+1}2\right\rfloor\right)$, $0 \le a_i,p_i < 998244353$.

Translated by ChatGPT 5