CF1452D.Radio Towers

There are $n + 2$ towns located on a coordinate line, numbered from $0$ to $n + 1$. The $i$-th town is located at the point $i$.

You build a radio tower in each of the towns $1, 2, \dots, n$ with probability $\frac{1}{2}$ (these events are independent). After that, you want to set the signal power on each tower to some integer from $1$ to $n$ (signal powers are not necessarily the same, but also not necessarily different). The signal from a tower located in a town $i$ with signal power $p$ reaches every city $c$ such that $|c - i| \lt p$.

After building the towers, you want to choose signal powers in such a way that:

• towns $0$ and $n + 1$ don't get any signal from the radio towers;
• towns $1, 2, \dots, n$ get signal from exactly one radio tower each.

For example, if $n = 5$, and you have built the towers in towns $2$, $4$ and $5$, you may set the signal power of the tower in town $2$ to $2$, and the signal power of the towers in towns $4$ and $5$ to $1$. That way, towns $0$ and $n + 1$ don't get the signal from any tower, towns $1$, $2$ and $3$ get the signal from the tower in town $2$, town $4$ gets the signal from the tower in town $4$, and town $5$ gets the signal from the tower in town $5$.

Calculate the probability that, after building the towers, you will have a way to set signal powers to meet all constraints.

在一条坐标轴上有 $n + 2$ 座城镇，编号从 $0$ 到 $n + 1$。第 $i$ 座城镇位于坐标点 $i$ 处。

你以概率 $\frac{1}{2}$ 在每座城镇 $1, 2, \dots, n$ 中独立地建造一座无线电塔（这些事件相互独立）。随后，你需要为每座已建造的塔设定一个信号功率，该功率为 $1$ 到 $n$ 之间的某个整数（各塔的信号功率不一定相同，但也未必互不相同）。一座位于城镇 $i$、信号功率为 $p$ 的塔，其信号可覆盖所有满足 $|c - i| \lt p$ 的城镇 $c$。

建好塔之后，你希望选择信号功率，使得满足以下条件：

• 城镇 $0$ 和 $n + 1$ 不接收到来自任何无线电塔的信号；
• 城镇 $1, 2, \dots, n$ 中的每一座城镇恰好接收到来自一座无线电塔的信号。

例如，若 $n = 5$，且你在城镇 $2$、$4$ 和 $5$ 建造了塔，则可将城镇 $2$ 处塔的信号功率设为 $2$，而将城镇 $4$ 和 $5$ 处塔的信号功率均设为 $1$。这样，城镇 $0$ 和 $n + 1$ 不接收任何信号；城镇 $1$、$2$、$3$ 接收来自城镇 $2$ 处塔的信号；城镇 $4$ 接收来自城镇 $4$ 处塔的信号；城镇 $5$ 接收来自城镇 $5$ 处塔的信号。

请计算：在建造完塔之后，存在一种设定信号功率的方式，使得所有约束均被满足的概率。

The first (and only) line of the input contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$).

输入的第一行（也是唯一一行）包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）。

Print one integer — the probability that there will be a way to set signal powers so that all constraints are met, taken modulo $998244353$.

Formally, the probability can be expressed as an irreducible fraction $\frac{x}{y}$. You have to print the value of $x \cdot y^{-1} \bmod 998244353$, where $y^{-1}$ is an integer such that $y \cdot y^{-1} \bmod 998244353 = 1$.

输出一个整数——满足所有约束条件的信号功率设置方式存在的概率，对 $998244353$ 取模。

形式上，该概率可表示为最简分数 $\frac{x}{y}$。你需要输出 $x \cdot y^{-1} \bmod 998244353$ 的值，其中 $y^{-1}$ 是满足 $y \cdot y^{-1} \bmod 998244353 = 1$ 的整数。

The real answer for the first example is $\frac{1}{4}$:

• with probability $\frac{1}{4}$, the towers are built in both towns $1$ and $2$, so we can set their signal powers to $1$.

The real answer for the second example is $\frac{1}{4}$:

• with probability $\frac{1}{8}$, the towers are built in towns $1$, $2$ and $3$, so we can set their signal powers to $1$;
• with probability $\frac{1}{8}$, only one tower in town $2$ is built, and we can set its signal power to $2$.

The real answer for the third example is $\frac{5}{32}$. Note that even though the previous explanations used equal signal powers for all towers, it is not necessarily so. For example, if $n = 5$ and the towers are built in towns $2$, $4$ and $5$, you may set the signal power of the tower in town $2$ to $2$, and the signal power of the towers in towns $4$ and $5$ to $1$.

第一个样例的真实答案是 $\frac{1}{4}$：

• 以概率 $\frac{1}{4}$，城镇 $1$ 和 $2$ 均建造了信号塔，因此可将它们的信号功率均设为 $1$。

第二个样例的真实答案是 $\frac{1}{4}$：

• 以概率 $\frac{1}{8}$，城镇 $1$、$2$ 和 $3$ 均建造了信号塔，因此可将它们的信号功率均设为 $1$；
• 以概率 $\frac{1}{8}$，仅在城镇 $2$ 建造了一座信号塔，因此可将其信号功率设为 $2$。

第三个样例的真实答案是 $\frac{5}{32}$。注意：尽管前述解释中对所有信号塔采用了相同的信号功率，但这并非必须。例如，若 $n = 5$，且信号塔建在城镇 $2$、$4$ 和 $5$，则可将城镇 $2$ 处信号塔的信号功率设为 $2$，而将城镇 $4$ 和 $5$ 处信号塔的信号功率均设为 $1$。