Maximizing Expected Rounds of Gobo Sort

In the famous Gobo sort, one shuffles a sequence randomly until it becomes sorted. More precisely, given a sequence a of length \(N\), one repeatedly does the following:

• Randomly generate a permutation \(p\) of \(\{1,2,\dots,N\}\) uniformly.
• Construct a new sequence \(b\) defined by \(b_i=a_{p_i}\) for \(1\le i\le N\).
• If \(b\) is sorted in non-decreasing order, stop and return \(b\); otherwise, repeat step 1.

The expected number of rounds (i.e. the number of times step 2 is executed) is the reciprocal of the probability that a random permutation produces a sorted sequence. For a multiset \(a\) with frequencies \(f_1,f_2,\ldots,f_k\) (so that \(\sum_{i=1}^k f_i=N\)), the number of distinct arrangements is \(\frac{N!}{f_1!f_2!\cdots f_k!}\) while there is exactly one sorted order. Hence the expected rounds is \[ E = \frac{N!}{f_1!f_2!\cdots f_k!}. \]

Now, you are given an initial sequence \(x\) of length \(n\). You are allowed to append exactly \(m\) positive integers, each chosen arbitrarily from the interval \([l, r]\). The final sequence has length \(n+m\). Let the frequency (multiplicity) of an integer be defined in the final sequence. The expected rounds of Gobo sort for the final sequence is \[ E = \frac{(n+m)!}{\prod_{v} (f_v)!}, \] where the product is taken over all distinct values in the final sequence. Since you can choose the appended \(m\) elements arbitrarily (subject to each being in \([l, r]\)), you want to maximize \(E\) by minimizing \(\prod_{v} (f_v)!\) over the numbers you can control. Note that the frequencies of numbers not in \([l, r]\) from the original sequence are fixed; you can only affect those for values in \([l, r]\).

It turns out that the optimal strategy is to distribute the appended numbers as evenly as possible among all integers in the range \([l, r]\), i.e. use a greedy strategy: at each addition, append the number with the current minimum frequency (if there is a tie, any choice works).

Your task is to compute the maximum possible expected round count modulo \(998244353\). Since the answer can be huge, you only need to output the result modulo \(998244353\).

Formally, let the final frequency of an integer \(v\) be \(f_v\) (if \(v\) does not appear in the final sequence then consider \(f_v = 0\)). You need to choose additional counts \(g(v)\) for every \(v \in [l, r]\) with \(\sum_{v=l}^{r}g(v)=m\) so that \(\prod_{v=l}^{r} (f_v + g(v))!\) is minimized. If you denote by \(A\) the product \[ A = \Bigl(\prod_{v \notin [l, r]} f_v!\Bigr) \times \Bigl(\prod_{v=l}^{r} (f_v + g(v))!\Bigr), \] then the answer is \[ \text{answer} = \frac{(n+m)!}{A} \pmod{998244353}. \]

inputFormat

The first line contains four integers \(n\), \(m\), \(l\) and \(r\) \( (1 \leq n,m \leq 10^5,\; 1 \leq l \leq r \leq 10^9)\), representing the length of the original sequence, the number of elements to append, and the range of numbers you can choose from respectively.

The second line contains \(n\) positive integers \(x_1, x_2, \dots, x_n\) representing the original sequence.

outputFormat

Output a single integer, the maximum possible expected round count modulo \(998244353\).

sample

3 2 1 3
2 3 1

30