你拥有一枚公平的硬币（即抛掷这枚硬币时，正面朝上和反面朝上的概率均为 50%）。你想要用它生成一个包含 $n$ 个整数的序列 $a_1, a_2, \dots, a_n$。为此，你需要重复以下过程恰好 $n$ 次：
- 不断抛掷硬币，直到出现反面为止。
- 假设在停止前你得到了 $k$ 次正面。
- 将整数 $k$ 加入序列的末尾。
对于一个整数序列 $b_1, b_2, \dots, b_m$，定义 $\text{mex}(b_1, b_2, \dots, b_m)$ 为最小的非负整数 $x$，满足：
- 对于每个 $1 \le i < x$，都存在 $1 \le j \le m$ 使得 $b_j = i$。
- 对于所有 $1 \le j \le m$，都有 $b_j \neq x$。
例如，$\text{mex}(0, 1, 0, 3) = 2$，$\text{mex}(4, 3, 2, 1, 0, 6, 7, 5) = 8$ 以及 $\text{mex}(1, 2, 3) = 0$。
现在，你需要计算 $\text{mex}(a_1, a_2, \dots, a_n)$ 的期望值，对 $998\,244\,353$ 取模。
输入格式
输入的第一行包含一个整数 $n$ ($1 \le n \le 10^5$)。
输出格式
输出一行，包含一个整数，表示答案对 $998\,244\,353$ 取模的结果。
样例
输入 1
1
输出 1
499122177
输入 2
3
输出 2
561512450
说明
在第一个样例中：
- 如果 $a_1 = 0$，则 $\text{mex}(a_1) = 1$。这种情况发生的概率为 $1/2$。
- 否则，$\text{mex}(a_1) = 0$。
因此，答案为 $1 \times \frac{1}{2} + 0 \times (1 - \frac{1}{2}) = \frac{1}{2} \equiv 499122177 \pmod{998\,244\,353}$。