Kujou Karen is a girl who loves to think.

Kujou Karen has recently been studying the properties of various sorting algorithms, and she discovered a very interesting sorting method: Gobo sort!

The algorithm for Gobo sort is roughly described as follows:

1. Suppose we want to sort a sequence $a$ of size $n$.
2. Generate a random permutation $p$ of size $n$ with uniform probability.
3. Construct a sequence $b$ of size $n$ such that $b_i = a_{p_i}$, check if $b$ is sorted. If $b$ is already sorted, terminate the algorithm and return $b$; otherwise, return to step 2.

Obviously, the expected time complexity of this algorithm is $O(n \times n!)$. However, Kujou Karen was surprised to find that, by utilizing the magical properties of quantum mechanics, the time complexity of this algorithm can be optimized to linear in a quantum system.

Kujou Karen conducted further research on this sorting algorithm and found that if a sequence satisfies certain properties, Gobo sort will calculate the correct result very quickly. To quantify this speed, she defined the number of execution rounds of Gobo sort as the number of times step 2 is executed.

Thus, she came up with the following problem:

There is a sequence $x$ of length $n$. Kujou Karen will append $m$ elements to this sequence, where each element is a positive integer in the range $[l, r]$. She wants the expected number of execution rounds of Gobo sort for the new sequence of length $n+m$ to be as large as possible. She wants to find this maximum expected number of rounds.

Kujou Karen is very clever and quickly calculated the answer. She wants to verify it with you. Since this expected number of rounds is extremely large, she only asks you to output the result modulo $998244353$.

Input

The first line contains an integer $T$, representing the number of test cases.

The next $2 \times T$ lines describe $T$ test cases.

Each test case consists of two lines. The first line contains four positive integers $n, m, l, r$, representing the length of the sequence, the number of elements to be added, and the range of the added numbers.

The second line contains $n$ positive integers, where the $i$-th integer is $x_i$.

Output

Output $T$ integers, representing the answers.

Examples

Input 1

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

Output 1

180
720

Note 1

For the first test case, we can add $\{1, 2, 2\}$ to the end of the sequence, making it 1 3 4 1 2 2. The probability of success in one round is $\frac{1}{180}$, so the expected number of rounds is 180.

For the second test case, we can add $\{5, 6, 7\}$ to the end of the sequence, making it 1 3 4 5 6 7. The probability of success in one round is $\frac{1}{720}$, so the expected number of rounds is 720.

Input 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

Output 2

2494800
138600
554400
821337882
821337882
10080
387491292
1320
6652800
900900

Subtasks

For $30\%$ of the data, $T \leq 10, n, m, l, r \leq 8$.

For $50\%$ of the data, $T \leq 300, n, m, l, r, a_i \leq 300$.

For $60\%$ of the data, $\sum{r-l+1} \leq 10^7$.

For $70\%$ of the data, $\sum{n} \leq 2 \times 10^5$.

For $90\%$ of the data, $m \leq 2 \times 10^5$.

For $100\%$ of the data, $T \leq 10^5, n \leq 2 \times 10^5, m \leq 10^7, 1 \leq l \leq r \leq 10^9$.

For $100\%$ of the data, $1 \leq a_i \leq 10^9, \sum{n} \leq 2 \times 10^6$.