题目描述

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

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

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

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

样例

input

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

output

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$ 。
对于 $100\%$ 的数据， $1\leq a_i\leq 10^9,\sum{n}\leq 2\times 10^6$ 。