C. Serial Representative
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

  • All series consisting of zeros: '0', '000', '00'. Sort by length and get '0', '00', '000'.
  • All series consisting of ones: '11', '1', '11', '1'. Sort by length and get '1', '1', '11', '11'.
  • Combine the obtained series preserving the relative order between blocks of zeros and ones. We get '1', '0', '1', '00', '11', '000', '11'. Write it as a string and get '101001100011'. This string is the serial representative of the original string '110100011001'.

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$$$.

Input

The first line of the input file contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$).

Output

Output a single integer — the number of required strings modulo $$$998\,244\,353$$$.

Examples
Input
3
Output
0
Input
4
Output
1
Note

The only binary string of length $$$4$$$ for which $$$S' \lt S$$$ holds is '1101'. Its serial representative is the string '1011'.