题目背景

半夏不是真正的夏天哦。但是，但是，我觉得现在的人生，就很幸福了。

看清楚自己想要什么吧。

题目描述

对于一个 01 串 $s$，将它切分成若干个子串，并且每个子串都是一个极长连续段。例如，$s = 0011100011$，那么它就会被切分成 $00$，$111$, $000$, $11$ 四个子串。随后，将 $0$ 的连续段和 $1$ 的连续段分别按照长度从小到大排序，再将它们按照原来的 01 顺序拼回去，得到一个新的 01 串 $t$。例如，对于上面的例子，$t = 0011000111$。

给定一个正整数 $n$，求所有长度为 $n$ 的 01 串 $s$ 中，有多少个在根据以上规则得到 $t$ 后满足 $t < s$。这里的小于号指字典序小于。

由于数量可能很多，你只需要输出答案对 $998244353$ 取模的结果。

输入格式

第一行一个正整数 $n$。

输出格式

一行一个整数，表示答案对 $998244353$ 取模的结果。

样例

样例输入 1

4

样例输出 1

1

样例输入 2

26

样例输出 2

33525046

数据范围与提示

本题共 $10$ 个测试点，每个测试点 $10$ 分。

对于所有数据，$1 \le n \le 5000$。