D. Радиовышки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

На координатной прямой расположено $$$n + 2$$$ города, с номерами от $$$0$$$ до $$$n + 1$$$. $$$i$$$-й город расположен в точке $$$i$$$.

В каждом из городов $$$1, 2, \dots, n$$$ с вероятностью $$$\frac{1}{2}$$$ строится радиовышка (эти события независимы). После этого вы хотите установить мощность сигнала каждой вышки равной целому числу от $$$1$$$ до $$$n$$$ (мощность сигнала не обязательно одинакова для всех вышек, но и не обязательно отличается). Сигнал с вышки, расположенной в городе $$$i$$$ с мощностью сигнала $$$p$$$, достигает каждого города $$$c$$$, что $$$|c - i| < p$$$.

После постройки вышек вы хотите выбрать мощность сигнала таким образом, чтобы:

  • города $$$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$$$.

Примеры
Входные данные
2
Выходные данные
748683265
Входные данные
3
Выходные данные
748683265
Входные данные
5
Выходные данные
842268673
Входные данные
200000
Выходные данные
202370013
Примечание

Настоящий ответ для первого примера — $$$\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$$$.