給定一個二分圖，其左右兩側各有 $n$ 個頂點。

在此圖中，左側的每個頂點都連接到右側頂點的一個前綴。具體來說，左側的第 $i$ 個頂點與右側的頂點 $1, 2, \dots, a_i$ 相連。

請找出此圖中頂點簡單環（vertex-simple cycles）的數量。若兩個環存在一條邊屬於其中一個環但不屬於另一個，則視為不同的環。

由於此數量可能很大，請輸出其對 $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