座位
题号：NC246842
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

房间内有 n 张椅子从 1 至 n 标号，有 n 个人从 1 至 n 标号，他们按标号 的顺序进入房间选位置坐。当第 i 个人坐下后，第 个人才会进入房间选位置坐。

第 i 个人会在标号在区间 范围内的椅子等概率随机选一张没有人坐的椅子坐下。

最终有 x 人，他们自身的标号与他们所坐椅子的标号相同，求 x 的期望，对 998244353 取模。

  • 可以证明，最终计算出来的期望可以被表示为分数形式 ，其中 P, Q 为整数且 。输出 即可。换句话说，输出这样一个整数 满足 。
  • 上式中的 符号表示同余符号。

输入描述:

第一行输入一个正整数 ，表示人（椅子）的数量。

输出描述:

输出一个整数表示，按上述规则落座，自身标号与所坐椅子标号相同的人数的期望。
示例1

输入

复制 
1

输出

复制 
1
示例2

输入

复制 
2

输出

复制 
1

说明

对于样例 2，第 1 个人进房间，会在 1 号椅子和 2 号椅子上选一个。
若他选择 1 号椅子（概率为 \frac{1}{2} ），那么第 2 个人只能选 2 号椅子，此时有 2 个人坐的椅子与自身标号相同。
若他选择 2 号椅子（概率也为 \frac{1}{2}），那么第 2 个人只能选 1 号椅子，此时没有人坐的椅子与自身标号相同。
因此，答案为 \frac{1}{2} \times 2 + \frac{1}{2} \times 0 = 1
示例3

输入

复制 
3

输出

复制 
748683266

说明

对于样例 3，令 p_i 表示第 i 个人坐的椅子标号，则以下三种情况发生的概率都是 \frac{1}{4}：

p = [1, 2, 3],~ p = [1, 3, 2],~ p = [2, 1, 3],~ p = [2, 3, 1]，在这三种情况中分别有 3, 1, 1, 0 个人标号与所坐椅子相同，因此答案为 \frac{3}{4}+\frac{1}{4}+\frac{1}{4}+\frac{0}{4} = \frac{5}{4}，在模 998244353 意义下计算出的结果是 748683266。
示例4

输入

复制 
1000

输出

复制 
499122427