正 $n$ 角形が与えられています。この正 $n$ 角形の $n$ 個の頂点に加え、時計回りに $i$ 番目の辺上には追加で $a_i-1$ 個の頂点があり、その辺を等分しています。つまり、第 $i$ 辺はこれらの頂点によって長さが等しい $a_i$ 個のセグメントに分割されています。

頂点間にいくつかの線分を引くことができます。ただし、線分を追加した後のグラフにおいて、新たに追加された任意の2つの線分は端点以外で交差してはならず、また、新しい線分は多角形の辺と重なってはなりません。

いくつかの線分を追加して得られたグラフを三角分割と呼ぶのは、多角形内のすべての面が三角形である場合のみです。なお、三角形の辺上には、元の凸多角形の辺上にあった頂点が存在しても構いません。

このような凸多角形が与えられたとき、上記の条件を満たす三角分割は何通りあるでしょうか。答えを $998\,244\,353$ で割った余りを求めてください。

入力

1行目に凸多角形の辺の数 $n$ が与えられます。

2行目に $n$ 個の正整数が与えられます。そのうち $i$ 番目の正整数は $a_i$ であり、問題文中の意味の通りです。

出力

条件を満たす三角分割の総数を $998\,244\,353$ で割った余りを1行で出力してください。

入出力例

入力 1

3
2 2 1

出力 1

5

注記 1

$5$ 通りの分割は図の通りです。

入力 2

5
3 1 4 2 5

出力 2

359895

入力 3

8
4 2 1 8 3 7 3 1

出力 3

577596154

小課題

$10\%$ のデータについて、$\sum a_i \leq 300$ を満たす。

$50\%$ のデータについて、$\sum a_i \leq 5\,000$ を満たす。

$100\%$ のデータについて、$n \geq 3$、$a_i \geq 1$、$\sum a_i \leq 5 \times 10^5$ を満たす。