На координатной прямой расположено \(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\).
Посчитайте вероятность того, что после постройки вышек у вас будет возможность установить мощность сигнала каждой из них, чтобы удовлетворить всем ограничениям.
Выходные данные
Выведите одно целое число — вероятность того, что найдется способ установить мощность сигнала так, чтобы все ограничения были выполнены, взятая по модулю \(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\).