Леха собрался в путь из Москвы в Саратов. Он не любит ездить на поездах, поэтому решил отправиться из одного города в другой на машине.
Путь из Москвы в Саратов может быть представлен, как прямая (пожалуй, она не столь ровная в действительности, но в данной задаче будем считать так), и расстояние между Москвой и Саратовом равно \(n\) км. Считаем, что Москва расположена в точке с координатой \(0\) км, а Саратов — в точке с координатой \(n\) км.
Вести машину столь долгое время достаточно утомительно. Формально, если Леха преодолел \(i\) километров после того, как останавливался на отдых в прошлый раз, то сложностью преодоления \((i + 1)\)-го километра он считает величину \(a_{i + 1}\). Гарантируется, что для каждого \(i \in [1, n - 1]\) \(a_i \le a_{i + 1}\). Сложность пути определяется, как сумма сложностей по каждому километру пути.
К счастью, между Москвой и Саратовом могут быть места для отдыха. Каждая целочисленная точка от \(1\) до \(n - 1\) может содержать место для отдыха. Когда Леха заезжает на место для отдыха, он (разумеется) отдыхает, и следующий километр для него становится сложности \(a_1\), километр после этого — сложности \(a_2\) и так далее.
Например, если \(n = 5\) и есть место для отдыха в точке с координатой \(2\), то сложность пути получится \(2a_1 + 2a_2 + a_3\): первый километр будет иметь сложность \(a_1\), второй — \(a_2\), потом Леха отдохнет, и третий километр будет иметь сложность \(a_1\), четвертый — \(a_2\) и последний — \(a_3\). Другой пример: если \(n = 7\) и есть места для отдыха в точках с координатами \(1\) и \(5\), то сложность пути Лехи будет равна \(3a_1 + 2a_2 + a_3 + a_4\).
Леха не знает, какие из целочисленных точек содержат места для отдыха. Поэтому он хочет предусмотреть любую возможную ситуацию. Очевидно, есть \(2^{n - 1}\) вариантов различных распределений точек отдыха (два распределения различны, когда существует такая точка \(x\), что место для отдыха есть ровно в одном из данных распределений). Леха считает все распределения равновероятными. Он хочет посчитать \(p\) — математическое ожидание сложности пути.
Очевидно, \(p \cdot 2^{n - 1}\) — это целое число. Посчитайте его по модулю \(998244353\).