C. Серийный представитель
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Определим серию бинарной строки как максимальную непрерывную подстроку этой строки, состоящей только из одного и того же символа, либо $$$0$$$, либо $$$1$$$. Например, в бинарной строке '110100011001' есть семь серий: '11', '0', '1', '000', '11', '00' и '1'.

Возьмем произвольную бинарную строку $$$S$$$ длины $$$n$$$ и рассмотрим все её серии. Отсортируем все её серии состоящие из нулей в порядке неубывания длины. Аналогично, отсортируем все серии состоящие из единиц. Затем объединим все эти серии сохраняя относительный порядок между блоками из нулей и единиц и получим новую строку $$$S'$$$. Назовем эту новую строку серийным представителем строки $$$S$$$.

Например, сделаем эту процедуру для строки '110100011001' приведенной выше:

  • Все серии состоящие из нулей: '0', '000', '00'. Отсортируем по длине и получим '0', '00', '000'.
  • Все серии состоящие из единиц: '11', '1', '11', '1'. Отсортируем по длине и получим '1', '1', '11', '11'.
  • Объединим полученные серии сохраняя относительный порядок между блоками из нулей и единиц. Получим '1', '0', '1', '00', '11', '000', '11'. Распишем как строку и получим '101001100011'. Эта строка является серийным представителем изначальной строки '110100011001'.

Вам дано одно целое число $$$n$$$. Вашей задачей является посчитать количество бинарных строк $$$S$$$ длины $$$n$$$ таких, что её серийный представитель $$$S'$$$ лексикографически меньше самой строки $$$S$$$ ($$$S' \lt S$$$). Поскольку ответ может быть очень большим, посчитайте его по модулю $$$998\,244\,353$$$.

Для двух строк $$$a$$$ и $$$b$$$ длины $$$n$$$, $$$a$$$ лексикографически меньше $$$b$$$ тогда и только тогда, когда существует такая позиция $$$i$$$, что $$$a_i \lt b_i$$$ и $$$a_j = b_j$$$ для всех $$$j \lt i$$$.

Входные данные

В первой строке входного файла дано одно целое число $$$n$$$ ($$$1 \le n \le 5000$$$).

Выходные данные

Выведите одно целое число — количество требуемых строк по модулю $$$998\,244\,353$$$.

Примеры
Входные данные
3
Выходные данные
0
Входные данные
4
Выходные данные
1
Примечание

Единственная бинарная строка длины $$$4$$$, для которой выполняется $$$S' \lt S$$$ это '1101'. Её серийным представителем является строка '1011'.