问题陈述

对于一个正整数 $N$，如果一个根为二叉树满足以下条件，则称之为度为 $N$ 的美丽二叉树。

• 每个顶点上都写有 $0$ 或 $1$。
• 每个叶子节点上都写有 $1$。
• 可以进行以下操作最多 $N-1$ 次，使得根节点上写有 $N$，其他顶点上都写有 $0$：
  • 选择顶点 $u$ 和 $v$，其中 $v$ 必须是 $u$ 的子节点或者" $u$ 的子节点的子节点"。令 $a_u \\gets a_u + a_v, a_v \\gets 0$，其中 $a_u$ 和 $a_v$ 分别是顶点 $u$ 和 $v$ 上的数字。

给定 $N$，求满足条件的度为 $N$ 的美丽二叉树的数量，模 $998244353$。

约束条件

• $1 \\leq N \\leq 10^7$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$

输出

输出答案。

示例输入 1

1

示例输出 1

1

满足条件的二叉树只有一个顶点，根节点上写有 $1$。

示例输入 2

2

示例输出 2

6

满足条件的二叉树如下图所示，共有六棵。

示例输入 3

222

示例输出 3

987355927

示例输入 4

222222

示例输出 4

675337738