Jerry jest ścigany przez Toma!

Aby uniknąć schwytania, Jerry musi wiedzieć, ile nor w jego domu może posłużyć za kryjówkę!

Dom Pani Dwóch Pantofli jest jednak zbyt duży. Dla uproszczenia zdefiniujmy iloczyn dwóch prostych grafów nieskierowanych $G_{1} =( V_{1} ,E_{1})$ oraz $G_{2} =( V_{2} ,E_{2})$ jako nowy graf $G_{1} \times G_{2} =\left( V^{*} ,E^{*} \right)$.

Zbiór wierzchołków $V^{*}$ nowego grafu to:

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

Zbiór krawędzi $E^{*}$ nowego grafu to:

$$ 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\} $$

Dla liczby całkowitej dodatniej $n$ oraz danych grafów $G_{1} ,G_{2} ,\dotsc ,G_{n}$, dom Pani Dwóch Pantofli można przedstawić jako:

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

Dla ułatwienia ucieczki (i dręczenia Toma), dla każdego spójnego komponentu, Jerry zawczasu połączył wszystkie nory, więc wystarczy policzyć je raz. Ponadto, dla każdej spójnej składowej istnieją nory.

Innymi słowy, musisz obliczyć liczbę spójnych składowych grafu $H$. Ponieważ Jerry zapomniał szczegółów każdego z grafów $G_k$, zakładamy, że w każdym grafie $G_k$ dowolna para wierzchołków jest połączona krawędzią z prawdopodobieństwem $\frac12$. Istnieje łącznie ${\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}}$ możliwych sposobów wyboru wszystkich grafów $G_k$.

Dla wygody należy wypisać wynik pomnożony przez ${\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}}$ modulo $998244353$.

Wejście

W pierwszej linii znajduje się liczba całkowita dodatnia $n$.

W drugiej linii znajduje się $n$ liczb całkowitych dodatnich, gdzie $k$-ta liczba to $m_k$, oznaczająca liczbę wierzchołków w $k$-tym grafie.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą wynik modulo $998244353$.

Przykład

Przykład 1

1
3

Wyjście 1

13

Uwagi 1

Zauważ, że dla $n=1$ zadanie sprowadza się do zsumowania liczby spójnych składowych wszystkich etykietowanych grafów nieskierowanych o $m_1$ wierzchołkach.

Przykład 2

2
2 3

Wyjście 2

73

Uwagi 2

Jeśli $G_1$ ma $0$ krawędzi, każdy graf $G_2$ prowadzi do $6$ spójnych składowych w $H$. Istnieje $8$ takich przypadków.

Jeśli $G_1$ ma $1$ krawędź, a $G_2$ ma $0$ krawędzi, $H$ ma $6$ spójnych składowych. Istnieje $1$ taki przypadek.

Jeśli $G_1$ ma $1$ krawędź, a $G_2$ ma $1$ krawędź, $H$ ma $4$ spójne składowe. Istnieją $3$ takie przypadki.

Jeśli $G_1$ ma $1$ krawędź, a $G_2$ ma $2$ krawędzie, $H$ ma $2$ spójne składowe. Istnieją $3$ takie przypadki.

Jeśli $G_1$ ma $1$ krawędź, a $G_2$ ma $3$ krawędzie, $H$ ma $1$ spójną składową. Istnieje $1$ taki przypadek.

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

Przykład 3

2
4 4

Wyjście 3

21565

Ograniczenia

Dla wszystkich danych testowych spełnione jest $1\le n, m_k\le 10^5$.