각 부분에 $n$개의 정점이 있는 이분 그래프가 주어집니다. 이 그래프에서 왼쪽 부분의 각 정점은 오른쪽 부분의 정점 중 일부 접두사(prefix)와 연결되어 있습니다. 즉, 왼쪽 부분의 $i$번째 정점은 오른쪽 부분의 $1, 2, \dots, a_i$번 정점들과 연결되어 있습니다.

이 그래프에 존재하는 정점 단순 사이클(vertex-simple cycle)의 개수를 구하세요. 두 사이클은 한쪽에는 포함되지만 다른 쪽에는 포함되지 않는 간선이 존재할 경우 서로 다른 것으로 간주합니다. 이 수는 매우 클 수 있으므로, $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