题目描述

$\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
4 2
1 1 2 2
1 2
1 4

1
3

1
10 5
3 5 3 3 6 4 8 2 3 5
6 9
1 8
8 10
4 9
7 7

4
748683272
3
665496241
1

提示

对于第一组样例：

第一个询问，取出的水晶颜色为 $[1, 1]$，只有一种排列，色段数为 $1$。

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