Se te da un grafo bipartito con $n$ vértices en cada parte.

En este grafo, cada vértice de la parte izquierda está conectado a un prefijo de vértices de la parte derecha. Específicamente, el $i$-ésimo vértice en la parte izquierda está conectado con los vértices $1, 2, \dots, a_i$ en la parte derecha.

Encuentra el número de ciclos simples (que no repiten vértices) en este grafo. Dos ciclos son diferentes si existe alguna arista que esté presente en uno pero no en el otro.

Como este número puede ser grande, encuéntralo módulo $998\,244\,353$.

Entrada

La primera línea de la entrada contiene un entero $n$ ($1 \le n \le 5000$): el número de vértices en cada parte.

La siguiente línea de la entrada contiene $n$ enteros $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$): una descripción del grafo dado.

Salida

Imprime un entero: el número de ciclos simples en el grafo dado, módulo $998\,244\,353$.

Ejemplos

Entrada 1

1
1

Salida 1

0

Entrada 2

2
2 2

Salida 2

1

Entrada 3

3
3 3 2

Salida 3

7

Entrada 4

10
6 6 7 7 8 8 9 9 10 10

Salida 4

410150080