CF1452D Radio Towers

在一条坐标线上有 $n+2$ 个城镇，编号从 $0$ 到 $n+1$。第 $i$ 个城镇位于点 $i$。 你会以概率 $\frac{1}{2}$（这些事件彼此独立）在每个 $1,2,\dots,n$ 号城镇各建一个无线电塔。之后，你想要为每个塔设置一个信号强度，信号强度是 $1$ 到 $n$ 之间的整数（不同塔的信号强度可以相同，也可以不同）。位于城镇 $i$ 的塔，信号强度为 $p$ 时，其信号可以覆盖所有满足 $|c-i| < 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$ 的塔的信号。 请计算：在建好所有塔后，存在一种信号强度的分配方式，使得所有条件都满足的概率。

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

输出一个整数，表示存在一种信号强度分配方式使所有条件都满足的概率，结果对 $998244353$ 取模。 形式化地说，概率可以表示为不可约分数 $\frac{x}{y}$。你需要输出 $x \cdot y^{-1} \bmod 998244353$，其中 $y^{-1}$ 是满足 $y \cdot y^{-1} \bmod 998244353 = 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$。 由 ChatGPT 4.1 翻译