P16923 [JLCPC 2026] 水晶城堡

$\mathit{tarjen}$ 是水晶城堡的守护者。城堡的长廊里镶嵌着一排 $n$ 颗魔法水晶，第 $i$ 颗水晶的颜色编号为 $a_i$。长廊中相邻且同色的水晶会产生共鸣，形成一个**色段**——即极大的连续相同颜色段。例如颜色序列 $[1, 1, 2, 2, 1]$ 有 $3$ 个色段：$[1, 1]$、$[2, 2]$ 和 $[1]$。 每天都有旅行者慕名前来，提出 $q$ 个问题。每个问题指定一段区间 $[l, r]$：如果把这段水晶取下来随机打乱重新排列（所有不同的颜色序列等概率出现），形成的色段数量的期望值是多少？ 答案对 $998244353$ 取模。即若答案为最简分数 $\dfrac{x}{y}$，输出 $x \cdot y^{-1} \bmod 998244353$。可以证明在本题约束下 $y^{-1}$ 总是存在的。

第一行有一个整数 $T$（$1 \le T \le 10^5$），表示数据组数。接下来 $T$ 段，每段描述一组数据： - 第一行两个整数 $n, q$（$1 \le n, q \le 10^5$）表示水晶数量和询问次数。 - 第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$）表示每颗水晶的颜色编号。 - 接下来 $q$ 行，每行两个整数 $l, r$（$1 \le l \le r \le n$）表示询问区间的端点。 数据保证 $\sum n\le 10^5$，$\sum q \le 10^5$。

对于每组数据中的每个询问，输出一行一个整数，表示期望色段数量对 $998244353$ 取模的结果。

对于第一组样例： 第一个询问，取出的水晶颜色为 $[1, 1]$，只有一种排列，色段数为 $1$。 第二个询问，取出的水晶颜色为 $[1, 1, 2, 2]$。$6$ 种排列的色段数分别为 $2, 4, 3, 3, 4, 2$，期望值为 $\dfrac{18}{6} = 3$。