Problem Description

You are given $n,m$ and two sequences $a_i$ and $p_i$ of length $n$. Some values of $a_i$ are fixed, while some are unknown. Each position also has a type, either $0$ or $1$. You need to assign values to the unknown $a_i$ so that $a_i \ge 1$ and $\sum a_i = m$.

For every possible assignment of $a$, consider the following game. Compute the sum of the game's weight over all assignments of $a$, modulo $998244353$.

• The game consists of $2^n$ rounds. At the beginning of the $x$-th round, the health of the $i$-th player, denoted by $b_i$, is set to $a_i$, and their type is determined by the $(i-1)$-th bit in the binary representation of $x-1$. Here, $x$ is indexed from $1$.

• At the beginning of each round, all people of type $1$ start moving to the right simultaneously, while people of type $0$ stay still. Everyone moves one cell per unit time.

• Whenever a type-$1$ person meets a type-$0$ person, suppose their indices are $i,j$, and let $t=\min(b_i,b_j)$. Then perform simultaneously: $b_i \leftarrow b_i - t,\ b_j \leftarrow b_j - t$. Any person with $b_i=0$ disappears.

• The weight of this round is the product of the initial $p$ values of all people still existing after $10^{100}$ units of time.

• The weight of the game is the sum of the weights of all $2^n$ rounds.

Input Format

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

The second line contains $n$ non-negative integers $a_i$, where $a_i=0$ indicates that this position is undetermined.

The third line contains $n$ positive integers $p_i$, representing the initial weight of each person.

Output Format

Output a single integer — the sum of the game weights over all valid assignments, modulo $998244353$.

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

Hint

Sample Explanation 1

The game lasts for $4$ rounds:

• In the $1$-st round, the types of the two players are $0$ and $0$. Both of them survive until the end, so the weight is $2 \times 2 = 4$.
• In the $2$-nd round, the types of the two players are $1$ and $0$. After $1$ unit of time, they collide, and their health becomes $0$ and $1$. Only the second player survives, so the weight is $2$.
• In the $3$-rd round, the types of the two players are $0$ and $1$. Both of them survive until the end, so the weight is $4$.
• In the $4$-th round, the types of the two players are $1$ and $1$. Both of them survive until the end, so the weight is $4$.

Thus, the answer is $4 + 2 + 4 + 4 = 14$.

Constraints

For all test cases, $1\le n,m\le 500$, $0\le a_i \le m$, $1\le p_i < 998244353$, and it is guaranteed that there exists at least one valid assignment of $a$.

• Special property: It is guaranteed that $m=n$.