E-「LAOI-19」春の湊に

时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 2016 幻想遊戯 <雅>「春の湊に」

$\hspace{15pt}$ 给定一个长为 $n$ 的正整数序列 $a,b$ ，并生成一个长为 $n$ 的序列 $c$ ，其中 $c_i$ 从 $[a_i,b_i] \cap \mathbb{Z}$ 中独立均匀随机生成。
$\hspace{15pt}$ 令 $x$ 为 $c$ 的前缀最大值序列， $y$ 为 $c$ 的后缀最大值序列。即 $x_i = \max\limits_{j=1}^i c_j$ 、 $y_i= \max\limits_{j=i}^n c_j$ 。

$\hspace{15pt}$ 现询问下式的期望值：

$\displaystyle\sum_{i=1}^n (x_i-y_i)^2$

$\hspace{15pt}$ 可以证明答案可以表示为一个不可约分数 $\tfrac{p}{q}$ ，为了避免精度问题，请直接输出整数 $\left(p \times q^{-1} \bmod M\right)$ 作为答案，其中 $M = 998\,244\,353$ ， $q^{-1}$ 是满足 $q\times q^{-1} \equiv 1 \pmod{M}$ 的整数。更具体地，你需要找到一个整数 $x \in [0, M)$ 满足 $x \times q$ 对 $M$ 取模等于 $p$ ，您可以查看样例解释得到更具体的说明。

$\hspace{15pt}$ 保证答案的逆元一定存在。

输入描述:

第一行输入一个正整数 。 
第二行输入  个正整数 。 
第三行输入  个正整数 。

除此之外，保证  且 。

输出描述:

输出一个整数，表示式子的期望值对  取模后的结果。

示例1

输入

复制

1
2
5

输出

复制

说明

在这个样例中， 序列始终相等，故答案期望为 。

示例2

输入

复制

2
1 1
1 3

输出

复制

665496237

说明

在这个样例中，可能的序列  有 、、，计算可得期望 ，对  取模后为 。

示例3

输入

复制

5
1 2 3 4 5
2 3 4 5 6

输出

复制

备注:

在几乎全部的情况下，PyPy 的运行速度优于 Python，我们建议您选择对应版本的 PyPy 进行提交、而不是 Python。