F. Фишки на прямой
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ фишек, и вы собираетесь разместить каждую из них в одной из $$$x$$$ точек, пронумерованных от $$$1$$$ до $$$x$$$. В каждой точке может находиться несколько фишек.

После размещения фишек вы можете выполнять следующие четыре операции (в любом порядке, любое количество раз):

  • выбрать фишку в точке $$$i \ge 3$$$, удалить ее и разместить две новых фишки: одну в $$$i-1$$$, одну в $$$i-2$$$;
  • выбрать две фишки в соседних точках $$$i$$$ и $$$i+1$$$, удалить их и разместить новую фишку в $$$i+2$$$;
  • выбрать фишку в точке $$$1$$$ и переместить ее в $$$2$$$;
  • выбрать фишку в точке $$$2$$$ и переместить ее в $$$1$$$.

Обратите внимание, что координаты фишек, которые вы размещаете во время операций, не могут быть меньше $$$1$$$, но могут быть больше $$$x$$$.

Обозначим стоимость размещения фишек как минимальное количество фишек, которое может остаться на прямой после выполнения этих операций, начиная с выбранного вами размещения.

Например, стоимость размещения двух фишек в точках $$$3$$$ и одной фишки в точке $$$5$$$ равна $$$2$$$, потому что вы можете уменьшить количество фишек до $$$2$$$ следующим образом:

  • выбрать фишку в точке $$$3$$$, удалить ее, разместить одну фишку в $$$1$$$ и одну фишку в $$$2$$$;
  • выбрать по одной фишке в точках $$$2$$$ и $$$3$$$, удалить их и разместить фишку в $$$4$$$;
  • выбрать по одной фишке в точках $$$4$$$ и $$$5$$$, удалить их и разместить фишку в $$$6$$$.

Вам даны три целых числа $$$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$$$:

  • $$$(1, 1)$$$;
  • $$$(1, 2)$$$;
  • $$$(1, 3)$$$;
  • $$$(2, 2)$$$;
  • $$$(2, 3)$$$.