CF1153F.Serval and Bonus Problem

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$.

越来越接近数学家的Serval，成为了加帕里大学（Japari University）的一名数学专业大学生。在微积分课上，老师教他如何计算给定线段的一个随机子线段的期望长度。随后，老师布置了一道附加题作为家庭作业，并以IOI车库套件作为奖励。这道附加题要求将该问题推广到如下一般情形：

给定一条长度为 $l$ 的线段。我们从该线段上等概率地随机选取 $n$ 条线段：每条线段由在线段上随机选取两个端点（端点坐标可以是非整数）并取其间的区间构成。你将得到随机线段的数量 $n$ 和另一个整数 $k$。这 $n$ 条随机线段共有 $2n$ 个端点，它们将原线段划分成 $(2n+1)$ 个小区间。你的任务是计算：被至少 $k$ 条随机线段覆盖的所有小区间的总长度的期望值。

你应输出答案对 $998244353$ 取模的结果。

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$).

第一行包含三个用空格分隔的正整数 $n$、$k$ 和 $l$（$1\leq k \leq n \leq 2000$，$1\leq l\leq 10^9$）。

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 \lt M$ and $x \cdot q \equiv p \pmod{M}$.

输出一个整数——在模 $998244353$ 意义下，被至少 $k$ 条随机线段覆盖的所有区间的总长度的期望值。

形式化地，令 $M = 998244353$。可以证明答案可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，请输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

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$.

在第一个例子中，期望的总长度为 $\int_0^1 \int_0^1 |x-y| \,\mathrm{d}x\,\mathrm{d}y = {1\over 3}$，而 $3^{-1}$ 对 $998244353$ 取模的结果为 $332748118$。