Джерри преследует Том!

Чтобы скрыться от преследования, Джерри нужно знать, сколько в доме мышиных нор, в которых можно спрятаться!

Дом мамочки Двух Тапочек слишком велик. Для простоты определим произведение двух простых неориентированных графов $G_{1} =( V_{1} ,E_{1})$ и $G_{2} =( V_{2} ,E_{2})$ как новый граф $G_{1} \times G_{2} =\left( V^{*} ,E^{*} \right)$.

Множество вершин нового графа $V^{*}$ определяется как:

$$ V^{*} = \left\{{(a,b)| a \in V_{1}, b \in V_{2}}\right\} $$

Множество ребер нового графа $E^{*}$ определяется как:

$$ E^{*} =\left\{\left(( u_{1} ,v_{1}) ,( u_{2} ,v_{2})\right) \mid ( u_{1} ,u_{2}) \in E_{1}, ( v_{1} ,v_{2}) \in E_{2}\right\} $$

Для натурального числа $n$ и заданных графов $G_{1} ,G_{2} ,\dotsc ,G_{n}$ дом мамочки Двух Тапочек можно представить как

$$ H = (((G_1 \times G_2) \times G_3) \times \cdots) \times G_n $$

Для удобства побега (и чтобы подразнить Тома), Джерри заранее соединил все мышиные норы в рамках одной компоненты связности, поэтому вам нужно посчитать их количество.

Иными словами, вам нужно найти количество компонент связности в $H$. Однако Джерри забыл детали каждого графа $G_k$, поэтому мы предполагаем, что в каждом $G_k$ любые две вершины соединены ребром с вероятностью $\frac12$. Всего существует ${\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}}$ способов выбрать все графы $G_k$.

Для удобства вам нужно вывести ответ, умноженный на ${\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}}$, по модулю $998244353$.

Входные данные

В первой строке вводится натуральное число $n$.

В следующей строке вводятся $n$ натуральных чисел, где $k$-е число — это $m_k$, количество вершин в $k$-м графе.

Выходные данные

Выведите одно целое число — ответ по модулю $998244353$.

Примеры

Пример 1

1
3

13

Примечание 1

Заметьте, что для случая $n=1$ задача сводится к сумме количеств компонент связности по всем помеченным неориентированным графам с $m_1$ вершинами.

Пример 2

2
2 3

73

Примечание 2

Если в $G_1$ $0$ ребер, то при любом $G_2$ в $H$ будет $6$ компонент связности; таких вариантов $8$.

Если в $G_1$ $1$ ребро, а в $G_2$ $0$ ребер, то в $H$ будет $6$ компонент связности; такой вариант $1$.

Если в $G_1$ $1$ ребро, а в $G_2$ $1$ ребро, то в $H$ будет $4$ компоненты связности; таких вариантов $3$.

Если в $G_1$ $1$ ребро, а в $G_2$ $2$ ребра, то в $H$ будет $2$ компоненты связности; таких вариантов $3$.

Если в $G_1$ $1$ ребро, а в $G_2$ $3$ ребра, то в $H$ будет $1$ компонента связности; такой вариант $1$.

$$ 6\times 8 + 6\times 1 + 4\times 3 + 2\times 3 + 1\times 1 = 73 $$

Пример 3

2
4 4

21565

Ограничения

Для всех тестовых данных выполняется $1\le n, m_k\le 10^5$.