灭霸并不喜欢传统排序算法。
对于一个长度为 $m$ 的序列 $a_1, a_2, \dots, a_m$，定义一次"灭霸排序"操作如下：
- 如果当前序列已经严格递增，即满足 $a_1 < a_2 < \dots < 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$ 取模后输出。
输入格式
输入仅一行一个整数 $N$ $(1 \le N \le 10^6)$，表示初始排列的长度。
输出格式
输出一行一个整数，表示 $\mathbb{E}[X]$ 对 $998244353$ 取模后的结果。
更形式化地，若 $\mathbb{E}[X]$ 的最简分数表示为 $\dfrac{P}{Q}$，则你需要输出 $P \cdot Q^{-1} \bmod 998244353$，其中 $Q^{-1}$ 表示 $Q$ 在模 $998244353$ 意义下的乘法逆元。
可以证明，在本题数据范围内，上述逆元一定存在。
样例
输入格式 1
2
输出格式 1
499122178
输入格式 2
4
输出格式 2
83187031
说明
- "排列"指由 $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}.$