在 Treeland，政府正在进行司法改革：他们需要选择一个新的司法层级结构。该层级结构将由 $n$ 名法官组成，法官被方便地标记为从 $1$ 到 $n$ 的整数。

司法层级结构是一棵有根的带标号树，其顶点即为法官。每位法官都有一个有序的直接下属列表：即有根树中的子节点。此外，司法层级结构中的每位法官要么是可靠的，要么是不可靠的。

如果对于每位法官，他本人及其所有直接下属中至少有一半是可靠的，则称该司法层级结构是“公平的”。

如果满足以下三个条件中的至少一个，则认为两个司法层级结构不同： 某位法官在一个层级结构中是可靠的，而在另一个中是不可靠的； 某位法官在一个层级结构中的直接下属集合与在另一个层级结构中的不同； * 某位法官在一个层级结构中不可靠下属的相对顺序与在另一个层级结构中的不同。

你可以查看说明部分以更好地理解这些条件。

政府希望通过遍历所有可能的选项来选择一个公平的司法层级结构。为了评估工作量，他们需要知道存在多少种不同的公平司法层级结构。请计算该数量对 $998\,244\,353$ 取模的结果。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 2 \cdot 10^5$)：层级结构中法官的数量。

输出格式

输出一个整数：具有 $n$ 名法官的公平司法层级结构的数量，对 $998\,244\,353$ 取模。

样例

样例输入 1

1

样例输出 1

1

样例输入 2

3

样例输出 2

24

样例输入 3

5

样例输出 3

3190

样例输入 4

100

样例输出 4

413875584

说明

以下是一些司法层级结构的示例，以阐明上述条件。

每位法官的直接下属放置在法官下方，从左到右排列。 可靠的法官为灰色，不可靠的法官为白色。

这两个公平的层级结构被认为是相同的：

这四个层级结构各不相同：