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), Jerry założył, że każda spójna składowa stanowi jedną kryjówkę, więc wystarczy policzyć je raz.

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$.