K. 灭霸排序 I
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

灭霸并不喜欢传统排序算法。

对于一个长度为 $$$m$$$ 的序列 $$$a_1, a_2, \dots, a_m$$$，定义一次"灭霸排序"操作如下：

  • 如果当前序列已经严格递增，即满足 $$$a_1 \lt a_2 \lt \dots \lt a_m$$$，则算法立即结束。
  • 否则，从当前序列的 $$$m$$$ 个位置中，等概率随机选择恰好 $$$\lfloor m / 2 \rfloor$$$ 个位置删除，保留其余元素的相对顺序，然后继续对剩余序列执行同样的过程。

注意，上述删除操作中的 $$$m$$$ 指的是当前序列长度，而不是初始长度。也就是说，若某一轮开始时当前还剩下 $$$m$$$ 个元素且序列尚未有序，那么这一轮就会随机删除其中的 $$$\lfloor m / 2 \rfloor$$$ 个元素。

现在，先等概率随机生成一个长度为 $$$N$$$ 的排列 $$$p_1, p_2, \dots, p_N$$$，然后对该排列执行灭霸排序。

设最终剩余元素个数为 $$$X$$$。你需要求出 $$$\mathbb{E}[X]$$$，并将答案对 $$$998244353$$$ 取模后输出。

Input

输入仅一行一个整数 $$$N$$$ $$$(1 \le N \le 10^6)$$$，表示初始排列的长度。

Output

输出一行一个整数，表示 $$$\mathbb{E}[X]$$$ 对 $$$998244353$$$ 取模后的结果。

更形式化地，若 $$$\mathbb{E}[X]$$$ 的最简分数表示为 $$$\dfrac{P}{Q}$$$，则你需要输出 $$$P \cdot Q^{-1} \bmod 998244353$$$，其中 $$$Q^{-1}$$$ 表示 $$$Q$$$ 在模 $$$998244353$$$ 意义下的乘法逆元。

可以证明，在本题数据范围内，上述逆元一定存在。

Examples
Input
2
Output
499122178
Input
4
Output
83187031
Note
  • "排列"指由 $$$1, 2, \dots, N$$$ 这 $$$N$$$ 个互不相同的整数组成的序列。
  • 所有随机选择均指在所有合法方案中等概率进行。
  • 删除元素后，剩余元素的相对顺序保持不变。

长度为 $$$2$$$ 的排列只有两种：

  • $$$[1, 2]$$$，此时序列已经有序，最终剩余元素个数为 $$$2$$$。
  • $$$[2, 1]$$$，此时序列无序，需要随机删除 $$$1$$$ 个元素。无论删除哪一个，剩余序列长度都为 $$$1$$$，且一定有序，因此最终剩余元素个数为 $$$1$$$。

所以 $$$\mathbb{E}[X] = \frac{2 + 1}{2} = \frac{3}{2}$$$。

模 $$$998244353$$$ 意义下，$$$\frac{3}{2} \equiv 3 \cdot 2^{-1} \equiv 499122178 \pmod{998244353}.$$$