F Balanced Grid Increments

制限時間: 2 sec メモリ制限: 1024 MB

Balanced Grid Increments

Statement

長さ \(N\) の正整数列 \(A = (A_1, A_2, \dots, A_N)\) が与えられます。 \(N\) 行 \(N\) 列のマス目があり、各マスには \(0\) が書かれています。

マス目に対して、以下の操作を \(0\) 回以上行います。

操作終了後のマス目が以下の条件をすべて満たすような操作列の個数を \(998244353\) で割ったあまりを求めてください。

Input

入力は以下の形式で標準入力から与えられます。

	\(N\)
	\(A_1~A_2~\dots~A_N\)

入力は以下の制約をすべて満たします。

Scoring

以下の追加制約を満たすデータセットに正解した場合、部分点が与えられます。

Examples

Input 1

2
4 1

Output 1

Input 2

3
1 1 1

Output 2

Input 3

10
1 1 2 3 5 8 13 21 34 55

Output 3

393485314

Note

\(1\) つ目の入出力例について、例えば以下のような操作方法が考えられます。