У вас есть $$$n$$$ фишек, и вы собираетесь разместить каждую из них в одной из $$$x$$$ точек, пронумерованных от $$$1$$$ до $$$x$$$. В каждой точке может находиться несколько фишек.
После размещения фишек вы можете выполнять следующие четыре операции (в любом порядке, любое количество раз):
Обратите внимание, что координаты фишек, которые вы размещаете во время операций, не могут быть меньше $$$1$$$, но могут быть больше $$$x$$$.
Обозначим стоимость размещения фишек как минимальное количество фишек, которое может остаться на прямой после выполнения этих операций, начиная с выбранного вами размещения.
Например, стоимость размещения двух фишек в точках $$$3$$$ и одной фишки в точке $$$5$$$ равна $$$2$$$, потому что вы можете уменьшить количество фишек до $$$2$$$ следующим образом:
Вам даны три целых числа $$$n$$$, $$$x$$$ и $$$m$$$. Вычислите количество размещений ровно $$$n$$$ фишек в точках от $$$1$$$ до $$$x$$$, имеющих стоимость, равную $$$m$$$, и выведите его по модулю $$$998244353$$$. Два размещения считаются разными, если количество фишек в какой-либо точке отличается между этими размещениями.
Единственная строка содержит три целых числа $$$n$$$, $$$x$$$ и $$$m$$$ ($$$1 \le m \le n \le 1000$$$; $$$2 \le x \le 10$$$).
Выведите одно целое число — количество размещений со стоимостью, равной $$$m$$$, взятое по модулю $$$998244353$$$.
2 3 1
5
42 10 5
902673363
1000 10 8
187821763
В первом примере существует пять способов разместить $$$2$$$ фишки в точках от $$$1$$$ до $$$3$$$, чтобы стоимость равнялась $$$1$$$:
Название |
---|