Sum of Minimum Reallocation Costs

You are given n boxes arranged in a row. Initially, the i-th box contains a_i goods so that the total number of goods is \(S = \sum_{i=1}^{n}a_i\). For any nonnegative integer array \((b_1, b_2, \ldots, b_n)\) with \(\sum_{i=1}^{n}b_i = S\), consider the following operation:

You want the i-th box to eventually contain exactly b_i goods. In order to achieve this, you are allowed to repeatedly perform the following operation: choose two adjacent boxes (boxes i and i+1, for \(1 \le i < n\)) and move exactly one good from one box to the other. The cost to perform an operation on boxes \(i\) and \(i+1\) is \(w_i\). Note: Moving one good from box \(i\) to box \(i+1\) or from box \(i+1\) to box \(i\) both incur a cost of \(w_i\). You must ensure that during any sequence of operations the number of goods in every box never becomes negative.

For each valid target distribution \((b_1, b_2, \ldots, b_n)\), define \(\operatorname{val}(b_1, b_2, \ldots, b_n)\) as the minimum cost required to reach that configuration from the initial state. Your task is to compute the sum of \(\operatorname{val}(b_1, b_2, \ldots, b_n)\) over all nonnegative integer arrays \((b_1, b_2, \ldots, b_n)\) satisfying \(\sum_{i = 1}^{n}b_i = S\). Since the answer can be very large, output it modulo \(998244353\).

Observation: It can be shown that the problem of achieving a configuration \((b_1, b_2, \ldots, b_n)\) optimally is equivalent to transporting the surplus/deficit along the line with cost equal to \[ \operatorname{val}(b_1, b_2, \ldots, b_n) = \sum_{i=1}^{n-1} w_i \cdot \left|\sum_{j=1}^{i}(a_j - b_j)\right|. \] By summing over all valid \(b\) arrays, the answer becomes \[ \sum_{i=1}^{n-1}w_i\left(\sum_{k=0}^{S} |A_i-k| \cdot f(i,k)\right)\quad\text{mod }998244353, \] where \(A_i = \sum_{j=1}^{i}a_j\) and \(f(i,k)\) is the number of ways to have \(\sum_{j=1}^{i}b_j = k\) and \(\sum_{j=i+1}^{n}b_j = S-k\). Note that \[ f(i,k)= \binom{k+i-1}{i-1} \cdot \binom{S-k+n-i-1}{n-i-1}. \]

inputFormat

The input consists of three lines:

• The first line contains a single integer \(n\) (the number of boxes).
• The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) representing the initial goods in each box.
• The third line contains \(n-1\) space-separated integers \(w_1, w_2, \ldots, w_{n-1}\) representing the cost to move a good between adjacent boxes.

outputFormat

Output a single integer – the sum of \(\operatorname{val}(b_1, b_2, \ldots, b_n)\) over all nonnegative integer arrays \((b_1, b_2, \ldots, b_n)\) with \(\sum_{i=1}^{n} b_i = S\), taken modulo \(998244353\).

sample

2
1 2
5

20