Определим серию бинарной строки как максимальную непрерывную подстроку этой строки, состоящей только из одного и того же символа, либо $$$0$$$, либо $$$1$$$. Например, в бинарной строке '110100011001' есть семь серий: '11', '0', '1', '000', '11', '00' и '1'.
Возьмем произвольную бинарную строку $$$S$$$ длины $$$n$$$ и рассмотрим все её серии. Отсортируем все её серии состоящие из нулей в порядке неубывания длины. Аналогично, отсортируем все серии состоящие из единиц. Затем объединим все эти серии сохраняя относительный порядок между блоками из нулей и единиц и получим новую строку $$$S'$$$. Назовем эту новую строку серийным представителем строки $$$S$$$.
Например, сделаем эту процедуру для строки '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'.