Леха собрался в путь из Москвы в Саратов. Он не любит ездить на поездах, поэтому решил отправиться из одного города в другой на машине.

Путь из Москвы в Саратов может быть представлен, как прямая (пожалуй, она не столь ровная в действительности, но в данной задаче будем считать так), и расстояние между Москвой и Саратовом равно $$$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$$$.