P16329 bloom


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.

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 a single integer — the sum of the game weights over all valid assignments, modulo $998244353$.

**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$. | Subtask | $n,m\le$ | Special Property | Score | | :-----: | :------: | :--------------: | :---: | | $1$ | $8$ | None | $10$ | | $2$ | $50$ | None | $20$ | | $3$ | $100$ | None | $20$ | | $4$ | $500$ | Yes | $20$ | | $5$ | $500$ | None | $30$ | - Special property: It is guaranteed that $m=n$.