Serval and Bonus Problem
Contest: Codeforces Round 551 (Div. 2)
Difficulty rating: 2600
Tags: combinatorics, dp, math, probabilities

Getting closer and closer to a mathematician, Serval becomes a university student on math major in Japari University. On the Calculus class, his teacher taught him how to calculate the expected length of a random subsegment of a given segment. Then he left a bonus problem as homework, with the award of a garage kit from IOI. The bonus is to extend this problem to the general case as follows.

You are given a segment with length $$$l$$$. We randomly choose $$$n$$$ segments by choosing two points (maybe with non-integer coordinates) from the given segment equiprobably and the interval between the two points forms a segment. You are given the number of random segments $$$n$$$, and another integer $$$k$$$. The $$$2n$$$ endpoints of the chosen segments split the segment into $$$(2n+1)$$$ intervals. Your task is to calculate the expected total length of those intervals that are covered by at least $$$k$$$ segments of the $$$n$$$ random segments.

You should find the answer modulo $$$998244353$$$.

Input format:
First line contains three space-separated positive integers $$$n$$$, $$$k$$$ and $$$l$$$ ($$$1\leq k \leq n \leq 2000$$$, $$$1\leq l\leq 10^9$$$).

Output format:
Output one integer — the expected total length of all the intervals covered by at least $$$k$$$ segments of the $$$n$$$ random segments modulo $$$998244353$$$.

Formally, let $$$M = 998244353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, the expected total length is $$$\int_0^1 \int_0^1 |x-y| \,\mathrm{d}x\,\mathrm{d}y = {1\over 3}$$$, and $$$3^{-1}$$$ modulo $$$998244353$$$ is $$$332748118$$$.

Example input:
1 1 1

Example output:
332748118

Example input:
6 2 1

Example output:
760234711

Editorial:
Without loss of generality, assume that $$$l=1$$$. For a segment covering, the total length of the legal segments is the probability that we choose another point $$$P$$$ on this segment randomly such that it is in the legal segments. Then all $$$2n+1$$$ points ($$$P$$$ and the endpoints of each segment) are chosen randomly and independently. So we only need to find the probability that point $$$P$$$ is in the legal segments. Note that only the order of these $$$2n+1$$$ points make sense. Because the points are chosen in the segment, the probability that some of them coincide is $$$0$$$, so we can assume that all points do not coincide.
Now the problem is, how to calculate the number of arrangements that $$$P$$$ is between at least $$$k$$$ pairs of endpoints. It can be solved by dynamic programming in time complexity of $$$O(n^2)$$$. We define $$$f(i,j,x)$$$ as the number of arrangements for the first $$$i$$$ positions, with $$$j$$$ points haven't been matched, and $$$P$$$ appeared $$$x$$$ times (obviously $$$x=0$$$ or $$$1$$$). So we can get three different types of transition for the $$$i$$$-th position below:
1. Place $$$P$$$ at $$$i$$$-th position (if $$$j\leq k$$$): $$$f(i-1,j,x)\rightarrow f(i,j,1)$$$
2. Start a new segment (if $$$i+j+x<2n$$$): $$$f(i-1,j-1,x)\rightarrow f(i,j,x)$$$
3. Match a started segment, note that we have $$$j$$$ choices of segments: $$$f(i-1,j+1,x)\times j\rightarrow f(i,j,x)$$$
Then $$$f(2n+1,0,1)$$$ is the number of legal arrangements. Obviously, the total number of arrangements is $$$(2n+1)!$$$. However, there are $$$n$$$ pairs of endpoints whose indices can be swapped, and the indices $$$n$$$ segments can be rearranged. So the final answer is $$$\frac{f(2n+1,0,1)\times n! \times 2^n}{(2n+1)!}$$$.