背景

题目描述

给定 $n,m$，和两个长为 $n$ 的序列 $a_i$ 和 $p_i$，$a_i$ 一些位置确定，一些不确定，每个位置有类型 $0,1$。你要给不确定的 $a_i$ 赋值，使得 $a_i \ge 1,\sum a_i=m$。求对于所有 $a$ 的赋值方式的以下游戏的权值和对 $998244353$ 取模的结果。

• 游戏将进行 $2^n$ 轮，第 $x$ 轮开始时第 $i$ 个人的血量 $b_i$ 设置为 $a_i$，类型为 $x-1$ 的二进制表示下第 $i - 1$ 位的值。$x$ 的取值从 $1$ 开始。

• 每轮开始时，所有类型 $1$ 的人开始同时往右走，类型 $0$ 的人不动，每过 $1$ 单位时间移动一格。

• 若一个类型 $1$ 碰到类型 $0$ 的点，设两人的编号为 $i,j$，$t = \min(b_i,b_j)$，同时执行 $b_i \leftarrow b_i - t,b_j \leftarrow b_j - t$，$b_i = 0$ 的人将会消失。

• 这一轮的权值为过了 $10^{100}$ 单位时间后所有存在的人的初始的 $p$ 的乘积。（若最后所有人死亡，则权值为 $1$）

• 游戏的权值为 $2^n$ 轮的权值之和。

输入格式

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

第二行 $n$ 个非负整数 $a_i$，其中 $a_i = 0$ 表示未确定的位置。

第三行 $n$ 个正整数 $p_i$ 表示每个人的初始权值。

输出格式

一行一个整数，表示所有情况的游戏权值之和。

2 3
1 2
2 2

14

4 4
1 1 0 0
2 2 3 3

239

6 10
0 1 1 0 0 2
743619643 294476845 718152187 194051637 59774782 188785641

285625840

提示

【样例解释 1】

游戏将进行 $4$ 轮：

• 第 $1$ 轮时，两个人的类型分别为 $0,0$，都能活到最后，权值为 $2\times 2 = 4$。

• 第 $2$ 轮时，两个人的类型分别为 $1,0$，此时在经过 $1$ 单位时间后两人相撞，生命值变为 $0,1$，只有第二个人活下来，权值为 $2$。

• 第 $3$ 轮时，两个人的类型分别为 $0,1$，都能活到最后，权值为 $4$。

• 第 $4$ 轮时，两个人的类型分别为 $1,1$，都能活到最后，权值为 $4$。

所以总权值为 $4+2+4+4=14$。

【数据范围】

本题使用子任务捆绑。

对于所有测试数据，$1\le n,m\le 500$，$0\le a_i \le m$，$1\le p_i < 998244353$，保证至少存在一组合法的 $a$。

特殊性质：保证 $m=n$。