Problem Description

$\mathit{tarjen}$ is the guardian of the Crystal Castle. In the castle corridor, there is a row of $n$ magic crystals. The color ID of the $i$-th crystal is $a_i$. Adjacent crystals with the same color will resonate and form a color segment, which is a maximal contiguous segment of the same color. For example, the color sequence $[1, 1, 2, 2, 1]$ has $3$ color segments: $[1, 1]$, $[2, 2]$, and $[1]$.

Every day, travelers come and ask $q$ questions. Each question specifies an interval $[l, r]$: if we take out the crystals in this interval and randomly shuffle them (all different color sequences appear with equal probability), what is the expected number of color segments after shuffling?

Output the answer modulo $998244353$. That is, if the answer is the reduced fraction $\dfrac{x}{y}$, output $x \cdot y^{-1} \bmod 998244353$. It can be proven that under the constraints of this problem, $y^{-1}$ always exists.

Input Format

The first line contains an integer $T$ ($1 \le T \le 10^5$), which is the number of test cases. Then there are $T$ blocks, each describing one test case:

• The first line contains two integers $n, q$ ($1 \le n, q \le 10^5$), representing the number of crystals and the number of queries.
• The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$), representing the color ID of each crystal.
• The next $q$ lines each contain two integers $l, r$ ($1 \le l \le r \le n$), representing the endpoints of the query interval.

It is guaranteed that $\sum n \le 10^5$ and $\sum q \le 10^5$.

Output Format

For each query in each test case, output one integer per line, representing the expected number of color segments modulo $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

Hint

For the first sample:

For the first query, the taken crystal colors are $[1, 1]$. There is only one permutation, and the number of color segments is $1$.

For the second query, the taken crystal colors are $[1, 1, 2, 2]$. The numbers of color segments for the $6$ permutations are $2, 4, 3, 3, 4, 2$, so the expected value is $\dfrac{18}{6} = 3$.

Translated by ChatGPT 5