各パートに $n$ 個の頂点を持つ二部グラフが与えられます。 このグラフにおいて、左側の各頂点は右側の頂点の接頭辞と接続されています。すなわち、左側の $i$ 番目の頂点は、右側の $1, 2, \dots, a_i$ 番目の頂点と接続されています。

このグラフにおける頂点単純閉路の数を求めてください。2つの閉路は、一方には含まれるがもう一方には含まれない辺が存在する場合に異なるとみなします。 この数は非常に大きくなる可能性があるため、$998\,244\,353$ で割った余りを求めてください。

入力

入力の最初の行には、各パートの頂点数である整数 $n$ ($1 \le n \le 5000$) が含まれます。 次の行には、与えられたグラフの記述である $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$) が含まれます。

出力

与えられたグラフにおける頂点単純閉路の数を $998\,244\,353$ で割った余りを整数で出力してください。

入出力例

入力 1

1
1

出力 1

0

入力 2

2
2 2

出力 2

1

入力 3

3
3 3 2

出力 3

7

入力 4

10
6 6 7 7 8 8 9 9 10 10

出力 4

410150080