#P18482. Hierarchies of Judges

Hierarchies of Judges

Hierarchies of Judges

树之国正在进行司法改革,政府需要选出一套新的司法层级。层级由 nn 位法官组成,法官用 11 到 nn 的整数编号。

司法层级是一棵有根的、顶点带有编号的树,顶点代表法官。每位法官都有一份有序的直属下级列表,也就是它在有根树中的孩子列表。此外,每位法官要么可靠,要么不可靠。

如果对于每位法官,在他本人及其所有直属下级之中,可靠者至少占一半,就称这个司法层级公平。恰好一半也满足条件。

如果满足以下三个条件中的至少一个,就认为两套司法层级不同:

  • 某位法官在其中一套层级中可靠,而在另一套层级中不可靠。
  • 某位法官在两套层级中的直属下级集合不同。
  • 某位法官的不可靠直属下级之间的相对顺序在两套层级中不同。

也就是说,只有不可靠孩子彼此之间的相对顺序参与区分;可靠孩子彼此的排列,以及可靠孩子与不可靠孩子之间的交错位置,都不会单独使两套层级不同。下方原图有助于理解这个等价关系。

政府想遍历所有不同的公平司法层级,以此选出新层级。请计算可选层级数量对 998 244 353998\,244\,353 取模的结果。

输入格式

输入一行,一个整数 nn(1≤n≤2⋅1051\le n\le2\cdot10^5),表示法官数量。

输出格式

输出一个整数,表示由 nn 位法官构成的不同公平司法层级数量对 998 244 353998\,244\,353 取模的结果。

原样例 1

1
1

原样例 2

3
24

原样例 3

5
3190

原样例 4

100
413875584

原图说明

每位法官的直属下级画在他的下方,从左到右对应给出的下级列表。灰色代表可靠,白色代表不可靠。

下图上方的两个公平层级被视为相同;下方的四个层级两两不同。

原题中相同及不同司法层级的示例