Merged Ball Sum Expectation

Consider n balls on a number line. The i-th ball is initially at position \(x_i\) and carries an associated number \(y_i\). Every second, each ball independently moves one step to the right with probability \(\frac{1}{2}\). When any ball reaches position \(T\), it is immediately removed and its number is added to a running total.

Moreover, during any second, if there exist two consecutive balls such that the left ball moves (i.e. steps right) while the right ball does not, these two balls merge into a single ball. The merged ball appears at the new position of the left ball and its number becomes the product of the two original numbers.

The process continues until all balls have been removed. Compute the expected value of the final total sum of the numbers collected at removal. Since the answer can be large, output it modulo \(998244353\).

Input Format

• The first line contains two integers \(n\) and \(T\).
• The second line contains \(n\) integers: \(x_1, x_2, \dots, x_n\) (the initial positions of the balls).
• The third line contains \(n\) integers: \(y_1, y_2, \dots, y_n\) (the numbers on the balls).

Output Format

• Output a single integer, the expected total sum (modulo \(998244353\)).

Note: All formulas are given in \(\LaTeX\) format.

inputFormat

The input begins with two integers \(n\) and \(T\). The next line contains \(n\) integers \(x_1, x_2, \dots, x_n\), and the following line contains \(n\) integers \(y_1, y_2, \dots, y_n\).

outputFormat

Output a single integer which is the expected sum of the numbers on the balls when all have been removed, modulo \(998244353\).

sample

1 3
1
5

5