| SDU Open 2023 |
|---|
| Finished |
Let us define a series of a binary string as the maximum continuous substring of this string consisting of only one character, either $$$0$$$ or $$$1$$$. For example, in the binary string '110100011001' there are seven series: '11', '0', '1', '000', '11', '00' and '1'.
Take an arbitrary binary string $$$S$$$ of length $$$n$$$ and consider all its series. Sort all its series consisting of zeros in non-decreasing order of length. Similarly, sort all series consisting of ones. Then combine all these series preserving the relative order between blocks of zeros and ones and obtain a new string $$$S'$$$. We call this new string the serial representative of the string $$$S$$$.
For example, let's do this procedure for the string '110100011001' given above:
You are given one integer $$$n$$$. Your task is to count the number of binary strings $$$S$$$ of length $$$n$$$ such that its serial representative $$$S'$$$ is lexicographically smaller than the string $$$S$$$ ($$$S' \lt S$$$). Since the answer can be very large, calculate it modulo $$$998\,244\,353$$$.
For two strings $$$a$$$ and $$$b$$$ of length $$$n$$$, $$$a$$$ is lexicographically smaller than $$$b$$$ if and only if there exists a position $$$i$$$ such that $$$a_i \lt b_i$$$ and $$$a_j = b_j$$$ for all $$$j \lt i$$$.
The first line of the input file contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$).
Output a single integer — the number of required strings modulo $$$998\,244\,353$$$.
3
0
4
1
The only binary string of length $$$4$$$ for which $$$S' \lt S$$$ holds is '1101'. Its serial representative is the string '1011'.
| Name |
|---|


