Dany jest wielokąt foremny o $n$ bokach. Oprócz $n$ wierzchołków tego wielokąta, na $i$-tym boku (licząc zgodnie z ruchem wskazówek zegara) znajduje się dodatkowo $a_i-1$ wierzchołków, które dzielą ten bok na równe części. Oznacza to, że $i$-ty bok został podzielony przez te wierzchołki na $a_i$ odcinków o równej długości.

Możesz łączyć wierzchołki odcinkami, przy czym po połączeniu dowolne dwa nowo dodane odcinki mogą przecinać się tylko w swoich końcach. Ponadto nowe odcinki nie powinny pokrywać się z bokami wielokąta.

Graf powstały po dodaniu pewnej liczby odcinków nazywamy triangulacją wtedy i tylko wtedy, gdy każda ściana wewnątrz wielokąta jest trójkątem. Zauważ, że na bokach trójkątów mogą znajdować się wierzchołki leżące pierwotnie na bokach wielokąta wypukłego.

Dla danego wielokąta wypukłego, ile istnieje triangulacji spełniających powyższe warunki? Oblicz liczbę sposobów modulo $998\,244\,353$.

Wejście

W pierwszej linii znajduje się liczba całkowita $n$, oznaczająca liczbę boków wielokąta wypukłego.

W drugiej linii znajduje się $n$ liczb całkowitych, gdzie $i$-ta liczba to $a_i$, zgodnie z opisem w treści zadania.

Wyjście

Wypisz jedną liczbę całkowitą oznaczającą liczbę triangulacji spełniających warunki zadania, modulo $998\,244\,353$.

样例数据

Przykład 1

Wejście:

3
2 2 1

Wyjście:

5

样例 1 解释

Istnieje $5$ sposobów, jak pokazano na rysunku.

Przykład 2

Wejście:

5
3 1 4 2 5

Wyjście:

359895

Przykład 3

Wejście:

8
4 2 1 8 3 7 3 1

Wyjście:

577596154

Podzadania

Dla $10\%$ danych wejściowych zachodzi $\sum a_i \leq 300$.

Dla $50\%$ danych wejściowych zachodzi $\sum a_i \leq 5\,000$.

Dla $100\%$ danych wejściowych zachodzi $n \geq 3$, $a_i \geq 1$ oraz $\sum a_i \leq 5 \times 10^5$.