F-小苯的数字分块_牛客周赛 Round 125

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

题目描述

$\hspace{15pt}$ 小苯认为「块」是数组中的一段极大连续相同段，满足段内元素均相等。
$\hspace{15pt}$ 同时数组的块数就是数组中「块」的个数。例如 $\{1,1,1,2,2,3,1,1\}$ 中， $\{1,1,1\}$ 、 $\{2,2\}$ 、 $\{3\}$ 、 $\{1,1\}$ 都是块，因此此数组的块数为 $4$ 。而其中 $\{1\}$ 、 $\{2,3\}$ 都不是块，因为 $\{1\}$ 不是极大的连续相同段，而 $\{2,3\}$ 并不是所有元素均相等。

$\hspace{15pt}$ 现在小红给了小苯一个长度为 $n$ 的被隐藏起来的数组 $a$ ，已知其中的每个元素 $a_i$ 都会独立地从闭区间 $[l_i,r_i]$ 中等概率随机选取一个整数值，你的任务就是求出 $a$ 数组块数的期望。
$\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$ ，您可以查看样例解释得到更具体的说明。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行输入一个整数  表示数组  的长度。
此后  行，第  行输入两个整数 ，表示  的取值范围。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据，新起一行输出一个整数，表示  数组的块数期望值对  取模后的结果。数据保证答案存在，即不会出现逆元不存在的情况。

示例1

输入

复制

输出

复制

2
798595487

说明

对于第一组测试数据，数组  有  的概率为 ，此时块数为 ；另有  的概率为  此时块数为 ，因此块数的期望为：。

对于第二组测试数据，通过枚举所有  种可能情况并计算块数，可以得到块数总和为 ，因此块数的期望为 。我们能够找到，，对  取模后恰好等于分子 ，所以  是需要输出的答案。