题目描述

在 Setsuna 的国家里，有 $n$ 座城市。它们在一条数线上按升序排列。城市 $i$ 在位置 $x_i$ 上。城市 $i$ 与城市 $j$ 之间的距离是 $|x_i-x_j|$ 。任意两个城市位于不同的位置。保证 $n$ 是偶数。 初始有 $n-1$ 条路， 第 $i$ 条路在城市 $i(1\le i \lt n)$ 和城市 $i+1$ 之间。

现在，这些 $n$ 城市想要建立关系。这些城市被分成 $\frac n2$ 对 $(a_i,b_i)(a_i \lt b_i)$ 。城市 $a_i$ 将与 $b_i$ 建立关系，然后在 $a_i$ 和 $b_i$ 之间建立一条路径。城市 $a$ 和城市 $b$ 之间的路径覆盖道路 $a\rightarrow a+1, a+1 \rightarrow a+2, ..., b-1\rightarrow b$ 。如果存在一个城市 $i$ ，在方案 $A$ 中与城市 $j$ 建立了关系，但在方案 $B$ 和 $j\not = k$ 中与城市 $k$ 建立了关系，则这两个方案 $A,B$ 称为不同方案。

但是，如果相邻城市之间的道路过多，有时会造成交通堵塞。为了解决这个问题，Setsuna 会提前给出每条道路的峰值。 第 $i$ 条道路的峰值是 $s_i$ ，这表明不能有超过 $s_i$ 条道路覆盖 $i\rightarrow i+1$ 道路。如果在一个方案中，没有一条道路的覆盖路径数超过它的峰值，我们就称这个方案有效。方案中的距离总和 $S$ 等于 $\sum_{i=1}^{n/2} |x_{a_i}-x_{b_i}|$ 。

现在 Setsuna 想知道，所有方案中 $S$ 的总和是多少。答案可能很大，请打印出以 $998244353$ 为模数的答案。

输入格式

第一行包含一个数字 $n\ (1\le n\le 2000)$ ，代表城市数量。

第二行包含 $n$ 个数字 $x_1,...,x_n\ (1\le x_i\le 10^9)$ 。 $x_i$ 代表城市 $i$ 的位置。

第三行包含 $n-1$ 个数字 $s_1,...,s_{n-1}\ (0\le s_i\le \frac n2)$ 。 $s_i$ 代表道路的顶点 $i\rightarrow i+1$ 。

输出格式

输出一个数字，表示答案取模 $998244353$ 。

6
1 3 4 6 9 10
1 2 2 1 2

19

解释 #1

样例中有三个方案。

方案 1： $(1,2),(3,4),(5,6),S=2+2+1=5$ 。

方案 2： $(1,3),(2,4),(5,6),S=3+3+1=7$ 。

方案 3： $(1,4),(2,3),(5,6),S=5+1+1=7$ 。

所以答案是 $\sum S=5+7+7=19$ 。