Bạn được cho một đồ thị hai phía với $n$ đỉnh ở mỗi phía.

Trong đồ thị này, mỗi đỉnh ở phía bên trái được nối với một tiền tố các đỉnh ở phía bên phải. Cụ thể, đỉnh thứ $i$ ở phía bên trái được nối với các đỉnh $1, 2, \dots, a_i$ ở phía bên phải.

Hãy tìm số lượng chu trình đơn (vertex-simple cycle) trong đồ thị này. Hai chu trình được coi là khác nhau nếu tồn tại một cạnh thuộc chu trình này nhưng không thuộc chu trình kia.

Vì số lượng này có thể rất lớn, hãy tìm kết quả theo modulo $998\,244\,353$.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa một số nguyên $n$ ($1 \le n \le 5000$): số lượng đỉnh ở mỗi phía.

Dòng tiếp theo chứa $n$ số nguyên $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$): mô tả của đồ thị đã cho.

Dữ liệu ra

In ra một số nguyên duy nhất: số lượng chu trình đơn trong đồ thị đã cho, theo modulo $998\,244\,353$.

Ví dụ

Dữ liệu vào 1

1
1

Dữ liệu ra 1

0

Dữ liệu vào 2

2
2 2

Dữ liệu ra 2

1

Dữ liệu vào 3

3
3 3 2

Dữ liệu ra 3

7

Dữ liệu vào 4

10
6 6 7 7 8 8 9 9 10 10

Dữ liệu ra 4

410150080