Mamy łańcuch składający się z $n+1$ wierzchołków, ponumerowanych od $0$ do $n$ wzdłuż łańcucha. Chcemy wyznaczyć liczbę cykli Eulera rozpoczynających się i kończących w wierzchołku $0$, takich że krawędź $(i-1, i)$ jest pokonywana dokładnie $2d_i$ razy. Wynik należy podać modulo $998244353$.

Wejście

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

W drugiej linii znajduje się $n$ liczb całkowitych dodatnich, gdzie $i$-ta liczba to $d_i$.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą liczbę sposobów modulo $998244353$.

Dane wejściowe

Dla $100\%$ danych wejściowych zachodzi $1\le n,d_i\le 10^5$.

Przykład

Wejście 1

2
2 1

Wyjście 1

2

Uwagi

Po wykonaniu jednego kroku można wybrać kontynuację ruchu w przód lub zawrócenie, a w dalszej części trasy wybór jest już jednoznaczny.

Wejście 2

4
200 30 8 11

Wyjście 2

812059605