题目背景

九条可怜是一个热爱思考的女孩子。

题目描述

九条可怜最近正在研究各种排序的性质，她发现了一种很有趣的排序方法： Gobo sort ！

Gobo sort 的算法描述大致如下：

• 假设我们要对一个大小为 $n$ 的数列 $a$ 排序。
• 等概率随机生成一个大小为 $n$ 的排列 $p$ 。
• 构造一个大小为 $n$ 的数列 $b$ 满足 $b_i=a_{p_i}$ ，检查 $b$ 是否有序，如果 $b$ 已经有序了就结束算法，并返回 $b$ ，不然返回步骤 2。

显然这个算法的期望时间复杂度是 $O(n\times n!)$ 的，但是九条可怜惊奇的发现，利用量子的神奇性质，在量子系统中，可以把这个算法的时间复杂度优化到线性。

九条可怜对这个排序算法进行了进一步研究，她发现如果一个序列满足一些性质，那么 Gobo sort 会很快计算出正确的结果。为了量化这个速度，她定义 Gobo sort 的执行轮数是步骤 2 的执行次数。

于是她就想到了这么一个问题：

现在有一个长度为 $n$ 的序列 $x$ ，九条可怜会在这个序列后面加入 $m$ 个元素，每个元素是 $[l,r]$ 内的正整数。 她希望新的长度为 $n+m$ 的序列执行 Gobo sort 的期望执行轮数尽量的多。她希望得到这个最多的期望轮数。

九条可怜很聪明，她很快就算出了答案，她希望和你核对一下，由于这个期望轮数实在是太大了，于是她只要求你输出对 $998244353$ 取模的结果。

输入格式

第一行输入一个整数 $T$，表示数据组数。

接下来 $2 \times T$ 行描述了 $T$ 组数据。

每组数据分成两行，第 1 行有四个正整数 $n,m,l,r$ ，表示数列的长度和加入数字的个数和加入数字的范围。 第 2 行有 $n$ 个正整数，第 $i$ 个表示 $x_i$ 。

输出格式

输出 $T$ 个整数，表示答案。

2
3 3 1 2
1 3 4
3 3 5 7
1 3 4

180
720

提示

###样例解释

对于第一组数据，我们可以添加 $\{1,2,2\}$ 到序列的最末尾，使得这个序列变成 1 3 4 1 2 2 ，那么进行一轮的成功概率是 $\frac{1}{180}$ ，因此期望需要 $180$ 轮。

对于第二组数据，我们可以添加 $\{5,6,7\}$ 到序列的最末尾，使得这个序列变成 1 3 4 5 6 7 ，那么进行一轮的成功概率是 $\frac{1}{720}$ ，因此期望需要 $720$ 轮。

数据范围

对于 30% 的数据， $T\leq 10 , n,m,l,r\leq 8$。
对于 50% 的数据， $T\leq 300,n,m,l,r,a_i\leq 300$ 。
对于 60% 的数据， $\sum{r-l+1}\leq 10^7$ 。
对于 70% 的数据， $\sum{n} \leq 2\times 10^5$ 。
对于 90% 的数据， $m\leq 2\times 10^5$。
对于 100% 的数据， $T\leq 10^5,n\leq 2\times 10^5,m\leq 10^7,1\leq l\leq r\leq 10^9$ ， $1\leq a_i\leq 10^9,\sum{n}\leq 2\times 10^6$ 。