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

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

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

1. 假设我们要对一个大小为 $n$ 的数列 $a$ 排序。
2. 等概率随机生成一个大小为 $n$ 的排列 $p$ 。
3. 构造一个大小为 $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$ 个整数，表示答案。

样例数据

样例 1 输入

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

样例 1 输出

180
720

样例 1 解释

对于第一组数据，我们可以添加 $\{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 轮。

样例 2 输入

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

样例 2 输出

2494800
138600
554400
821337882
821337882
10080
387491292
1320
6652800
900900

子任务

对于 $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$ 。

对于 $100\%$ 的数据， $1\leq a_i\leq 10^9,\sum{n}\leq 2\times 10^6$ 。