题目背景

何以撕裂，何以抹消？

题目描述

给定一个长为 $n$ 的整数序列 $a_1,a_2,\dots,a_n$，再给定一个有理数序列 $p_1,p_2,\dots,p_n$。每个位置上有一个随机系数 $c_i \in \{0,1\}$，其中 $P(c_i = 1) = p_i$，$P(c_i = 0) = 1-p_i$。

注意到随机系数写作序列后可以划分为若干个极长的连续 $0$、$1$ 段，极长指不能再向两边扩展。定义一种系数序列的权值为：当系数序列中恰有 $k$ 个极长连续 $1$ 段时为 $\sum\limits_{i=1}^n c_i a_i$，否则为 $0$。

求这个系数序列的期望权值。答案对 $998244353$ 取模。

输入格式

第一行，两个正整数 $n,k$。

第二行，$n$ 个非负整数 $a_1,a_2,\dots,a_n$。

第三行，$n$ 个非负整数 $p_1,p_2,\dots,p_n$，以模 $998244353$ 意义下给出。

输出格式

一行，一个非负整数，表示期望。

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

15

3 2
1 2 3
499122177 499122177 499122177

499122177

提示

样例解释

对于第一组样例，$c_i$ 必然为 $1$，且必然恰有 $1$ 个极长连续段，故权值必然为 $1 + 2 + 3 + 4 + 5 = 15$。

对于第二组样例，仅有 $c_1 = 1,c_2 = 0,c_3 = 1$ 时权值不为 $0$，且此种情况的概率为 $\frac 12 \times \frac 12 \times \frac 12 = \frac 18$，故期望为 $\frac{1+3}8 = \frac 12 \equiv 499122177 \pmod {998244353}$。

数据范围

对于 $30\%$ 的数据，$n \le 20$。

对于 $60\%$ 的数据，$n \le 10^3$。

对于 $100\%$ 的数据，$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$。