Gene Sample Research Value Sum

To help おとさか ゆう recover his memory, ともり なお has found PZY. After extensive experiments, PZY discovered that one’s ability is determined by certain ability genes in the body. There are in total \(m\) ability genes, labeled from \(1\) to \(m\). These genes are partitioned into \(n\) groups. In particular, the \(i\)-th group contains \(a_i\) genes with labels from \(\Bigl(\sum_{j=1}^{i-1}a_j\Bigr)+1\) to \(\sum_{j=1}^{i}a_j\).

A sequence is called a gene sample if and only if:

• The sequence consists only of numbers between \(1\) and \(m\).
• For every \(1 \le i \le n\), consider the subsequence formed by the numbers that belong to the \(i\)-th group. This subsequence must be non-decreasing (i.e. if there are \(k\) such numbers \(x_1, x_2, \dots, x_k\) then \(x_1 \le x_2 \le \cdots \le x_k\)), and the total number of occurrences of numbers from the \(i\)-th group is at most \(b_i\).

The research value of a gene sample is defined as the sum of all of its numbers (with repeated numbers counted separately). PZY wants to know the sum of the research values of all gene samples, modulo \(998244353\).

You are given \(n\), \(a_1,a_2,\ldots,a_n\), and \(b_1,b_2,\ldots,b_n\). Note that \(m = \sum_{i=1}^{n}a_i\). Compute the required sum modulo \(998244353\).

inputFormat

The first line contains a single integer \(n\) (the number of groups).

The second line contains \(n\) integers \(a_1,a_2,\ldots,a_n\), where \(a_i\) is the number of genes in group \(i\).

The third line contains \(n\) integers \(b_1,b_2,\ldots,b_n\), where \(b_i\) is the maximum number of times any gene from group \(i\) can appear in the sample.

outputFormat

Output a single integer representing the sum of research values of all gene samples modulo \(998244353\).

sample

1
3
1

6