#P17645. 计树

计树

题目描述

求有多少不同的包含 nn 个点的有标号无根树,满足:对于任何一个点 xx,都存在点 yy 使得 xx 和 yy 之间有一条边且 ∣x−y∣=1|x - y| = 1。答案对 998244353998244353 取模。

输入格式

一行一个正整数 nn。

输出格式

一行一个整数,所求答案。

输入输出样例 #1

输入 #1

4

输出 #1

4

输入输出样例 #2

输入 #2

209

输出 #2

21754876

输入输出样例 #3

输入 #3

5

输出 #3

11

输入输出样例 #4

输入 #4

6

输出 #4

56

说明/提示

【样例解释 #1】

无标题.png

样例 #1 中符合题意的 44 种树如上图所示。


【数据范围】

本题包含 2020 个测试点,每个测试点 55 分。

测试点编号 nn 的范围
1∼21 \sim 2 ≤7\leq 7
3∼43 \sim 4 ≤14\leq 14
5∼85 \sim 8 ≤30\leq 30
9∼129 \sim 12 ≤103\leq 10^3
13∼2013 \sim 20 ≤105\leq 10^5

对于所有测试点满足 nn 为正整数且 2≤n≤1052 \leq n \leq {10}^5。