Codeforces Round 551 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

dp

math

probabilities

*2600

No tag edit access

The problem statement has recently been changed. View the changes.

×
F. Serval and Bonus Problem

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputGetting 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

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

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

Examples

Input

1 1 1

Output

332748118

Input

6 2 1

Output

760234711

Input

7 5 3

Output

223383352

Input

97 31 9984524

Output

267137618

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2024 21:47:00 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|